5043：Escape

As a young man, Al was a skilled artist, a potter with a wife and two fine sons. One night, his older son developed a severe stomachache. Thinking it was only some common intestinal isorder, neither Al nor his wife took the condition very seriously. But the boy died suddenly that night.

Knowing the death could have been avoided if he had only realized the seriousness of the situation, he always felt he was guilty. To make matters worse, his wife left him a short time later, leaving him alone with his six-year-old younger son. The hurt and pain of the two situations were more than Al could stand, and he turned to alcohol for help. In time Al became an alcoholic.

As the alcoholism progressed, AL began to lose everything he possessed – his land, house, etc. Finally Al died alone in a small bar. Hearing of Al’s death, I thought, “What a totally wasted life! What a complete failure! ”

As time went by, I began to revalue my earlier rough judgement. I knew Al’s now adult son, Ernie. He is one of the kindest, most caring, most loving men I have ever known. I saw the love between Ernie and his children, thinking that kindness and caring had to come from somewhere.

I hadn’t heard Ernie talked much about his father. One day, I worked up my courage to ask him what on earth his father had done so that he became such a special person. Ernie said quietly, “As a child until I left home at 18”, Al came into my room every night, gave me a kiss and said, “love you, son.”

Tears came to my eyes as I realized what I had been a fool to judge Al as a failure. He had not left any material possessions behind. But he had been a kind loving father, and left behind his best love.

wuyiqi trapped in a maze again. He want to escape from the maze. He face a problem:

put k₁ + k₂ + ... + k_N different balls into N different boxes, the first box must contain k₁ balls, the second box must contain k₂ balls, and so on. What is the number of division modulo P (P is a prime.)..

This problem is too easy. wuyiqi can solve it very fast.

But wuyiqi can not escape from the maze, he must solve a hard problem.

Now there is the problem:

Given the N and P as mentioned above.

wuyiqi should gives the {k₁, k₂, ...k_N }make the above problem’s answer is zero.

And restriction conditions are 0 ≤ k₁ ≤ K₁, 0 ≤ k₂ ≤ K₂, ..., 0 ≤ k_N ≤ K_N , of course they are all integers, and at least one of which is not zero.

wuyiqi want you to calculate how many {k₁, k₂, ...k_N } meet the conditions.

The first line of the input is T (1 ≤ T ≤ 50), which stands for the number of test cases you need to solve.

For each case, there are two lines.

The first line of each case contains two integers N ,P (1 ≤ N ≤ 10, 1 ≤ P ≤ 20),as explained above, and the P is a prime.

The second line contains N integers, K₁, K₂, ..., K_N (1 ≤ K_i ≤ 10⁹).

For each case, you should output a single line, first output “Case #t: ”, where t indicating the case number between 1 and T . Then a single integer follows, indicating the answer module 100000009.