I was given this question in my interview but couldn't crack it.

Please go through it and help me out.

As we know in Fibonacci series every number after the first two is the sum of the two preceding ones.

Instead of adding two preceding numbers, multiply them and print the result modulo 10^9+7.

Since this is easy, let’'s make it bit difficult. Let'’s say there are K numbers to begin with.

You have to find nth number, where nth number will be product of k previous numbers modulo 10^9+7.

1<=t<=10

1<=n<=10^6

1<=k<=10

1<=k<=100

First line contains T number of test case,

In each test case

First line contains two integers n, k delimited by space

Second line contains k integers delimited by space

T lines, each line contains modified Fibonacci number modulo 109+7

Example 1

Input

1

10 3

1 2 3

Output

845114970

4th , 5th , 6th modified Fibonacci numbers are 6 , 36 , 648 respectively

Similarly 10th modified Fibonacci number will be 845114970

Help me out here please.

Thank You.

Please go through it and help me out.

As we know in Fibonacci series every number after the first two is the sum of the two preceding ones.

Instead of adding two preceding numbers, multiply them and print the result modulo 10^9+7.

Since this is easy, let’'s make it bit difficult. Let'’s say there are K numbers to begin with.

You have to find nth number, where nth number will be product of k previous numbers modulo 10^9+7.

**Constraints**1<=t<=10

1<=n<=10^6

1<=k<=10

1<=k<=100

**Input Format**First line contains T number of test case,

In each test case

First line contains two integers n, k delimited by space

Second line contains k integers delimited by space

**Output**T lines, each line contains modified Fibonacci number modulo 109+7

**Explanation**Example 1

Input

1

10 3

1 2 3

Output

845114970

**Explanation**4th , 5th , 6th modified Fibonacci numbers are 6 , 36 , 648 respectively

Similarly 10th modified Fibonacci number will be 845114970

**My Solution**:
C:

```
#include<stdio.h>
#define Modulo 1000000007
long long int Num2Mod(long long int A,long long int B);
main()
{
int K[10],n,k,i,j,t,first,second =1;
long long int product,list[1000000];
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&k);
for(i=0;i<k;i++)
{
scanf("%d",&K);
list=K;
}
for(i=0;i<n-2;i++)
{
product = 1;
for(j=0;j<k;j++)
product = Num2Mod(product,list[i+j]);
list[i+k] = product;
}
printf("%lld\n",list[n-1]);
}
}
long long int Num2Mod(long long int A,long long int B)
{
return ((A%Modulo*B%Modulo)%Modulo);
}
```

Help me out here please.

Thank You.

Last edited by a moderator: