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

#### Sample Output

#### Source

Dshawn

#### Manager