Query regarding no. of possible arrangements??

general
, ,
#1

I have n sets with different no. of elements in each set. I want to compute no. of ways of choosing captain from each one of them modulo 109+7.

This means, from each set I have to chose one captain and then in how many ways captains from each set can be selected and since the no. of ways will be large I have to calculate modulo with 109+7.

what could be the most efficient way to compute this.

Thanks in advance.

1 Like
#2

Suppose A[N] is the array with N elements and A[i] represent the number of elements in the i’th set. So we can choose one captain from the i’th set by A[i] ways. That means, our ultimate answer will be A[0] * A[1] * A[2] * … * A[N-1]. This number will be very large. So, we have to perform the modulo algorithm in every step of multiplication, like

ans=1
for i=0 to N-1
   ans = ans * A[i]
   ans = ans % 1000000007
2 Likes
#3

@debjitdj

dude it will cause number to overflow.

#4

It will work for A[i]<=10^9. And for greater numbers, you have to take those numbers in strings and have to define multiplication function for strings.