SP19084 DUKKAR2 - Huge Pascal triangle

Given **_P_** a prime number, and **_N_** an integer, [Dukkar](http://www.spoj.com/problems/DUKKAR/) found a really fast way to compute how many numbers are divisible by **_P_** on the **_N_** $ ^{th} $ row of the Pascal triangle. Now the task will be much harder : it's for all the **_N_** first rows. Moreover **_N_** will be a giant number, given in base **_P_** for convenience.

The first line of input contains an integer **_T_**, the number of test cases. Follow 2×**_T_** lines. For each test case, on the first line your are given two integers **_P_** and **_k_**. On the second line you are given **_k_** integers : the digits of **_N_** in base **_P_**. **_N = a $ _{0} $ ×P $ ^{0} $ + ... + a $ _{i} $ ×P $ ^{i} $ + ... + a $ _{k-1} $ ×P $ ^{k-1} $_**

For each test case, you have to print the number of numbers in all the first **_N_** rows of the Pascal triangle that are divisible by **_P_**. As the answer could not fit in a 64bit container, give your answer modulo 1000000007.