Efficient Bomber

All submissions for this problem are available.
The Army of CodeLand has a special canon which can be loaded with many different type of bombs. Each bomb can kill different number of enemy soldiers. The problem is tell in how many ways the enemy soldiers can be killed , with the given special bombs which kill different number of enemy soldiers.
Input
The first line contains the number of the test cases T(<=100). Each test case consists of 2 lines. The first line defines the number of enemy soldiers N (1<=N<=10^18) which tells us the number of enemies need to be killed. The next line contains k the number of types of bombs which are loaded in the canon, k (k<=15) integers follow in the same line each denoting number of enemy soldiers it can kill L (L<=15) enemies which can be killed by the bomb. .
Output
Output description.
 For each test case, output a single line containing the number of ways the enemies can be killed using specified bombs.
 Print the remainder obtained on dividing the answer by 1000000007 if the answer is greater than or equal to 1000000007
Example
Input: 3 10 1 1 12 2 1 5 15 5 1 2 3 4 5 Output: 1 15 13624
Explanation
In the given example first line contains number of test cases i.e. 3. Second line gives the number of enemies to be killed which is 10. Followed by next line which shows there is 1 type of bomb that can be loaded in the canon each killing one enemy.Similarly next cases which has 2 types of bombs each killing 1 and 5 enemies.... The output has number of ways these bombs can be used to kill all the enemies(10) . In first case there is only one way of killing all enemies that is using one bomb for one person and 415 ways in the second round. ...
Author:  swarajsaaj 
Tags  swarajsaaj 
Date Added:  28032013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 