Migrated from Lutece 452 BG

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Wangkun has to treat his friend gleiz a meal for he has got an offer from PKU.

Wangkun has $M$ yuan in his pocket and of course gleiz wants to spend all of them for the meal, and they want to order at least $K$ dishes for the abundance of the cuisine.

Now you are shown the menu which gives you the prices of all the dishes in the restaurant. Your task is to figure out the number of plans that help gleiz spend all wangkun's money to fulfill his appetite!

Input

There are multiple cases.

The first line of a case contains $3$ integers $N$ and $K$ and $M$($1\leq K\leq N\leq 38$, $1\leq M\leq 38\times 10^9$), the number of dishes in the restaurant.

The second line of a case contains $N$ integers $P_1, P_2,\cdots , P_N$ ($1\leq P[i]\leq 10^9$), giving you the prices of the dishes respectively.

It is ensured that all the prices are distinct.

Output

For each case you should output the number of plans in a line.

Samples

5 1 5
5 4 3 2 1
4 2 3
1 2 4 8
4 2 1
1 2 4 8

3
1
0

Resources

5th BUPT Programming Contest Final