Can you ac shiniu's shenti?

Time Limit: 16000/8000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

shiniu is a good student, he work hard when he was in buaa, this time his teacher want to give him a huge number of candies (infinity)!!!

However , shiniu's hands are really small! They can only hold K candies at the same time. Coincidently, shiniu finds that there are K kinds of candies given by his teacher.The number of every kind of candy is infinite.
shiniu loves eating candies , so everyday he eats a candy and then takes a candy from his teacher. shiniu loves "no zuo no die" ! He hates to hold more than M candies of same kind in his hands.
Now he wants to spend N days  eating and taking. Can you tell him how many ways she can spend these days?
By the way , shiniu is a little bit lazy , he wants you to tell him the answer mod 19921214.
 

Input

There is a number T on the first line which shows there are T cases below.
For each test case , there are 3 integers N K M on the first line.
And there are K integers below Ai shows the number of ith kind of candy is Ai.
It's guarantee that Sum{Ai} = K , and M >= Ai >= 0.

1 <= N <= 1e16 , 1 <= M , K <= 11

(shiniu is a god , so don't be too amazed at his age)

Output

For each test case , you should output a number on a single line.

Sample Input

2
1 2 1
1 1
1 2 2
1 1

Sample Output

2
4

Source

Dshawn

Manager

Information
Solved Number15
Submit Number49
Problem Tags
matrices
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel