TopCoder

Thumb img 0133
WTF!
我好廢啦晡賴補

User's AC Ratio

25.0% (1/4)

Submission's AC Ratio

8.3% (1/12)

Tags

Description

隨著時間的進展,終於來到了這一刻,$n$位勇者準備前往挑戰最終的魔王。
雖然一路上靠著大家強大的攻擊力輾了過去,但是魔王早就料到了這一刻,為了避免被眾人強大的火力打敗,魔王向H.C.求來了一個特別的能力:「一擊斃命」,除了可以將勇者們全部一擊斃命外,更可以保護自己,使得唯有同時受到恰與自己血量相等的傷害才會死亡。
身為最強勇者的你當然早就調查到這件事了(事實上你只是買了一本攻略書),為了避免被滅團你也請來了「黑澤露比」幫大家助陣,因為大家都很喜歡露比,所以只要聽到「頑張ルビィ!」(加油露比),攻擊力馬上就會從$x$變成$x!$ (也就是 $\prod_{i=1}^ {x} i $),不過對於每個人,露比只願意幫他加油一次,而且因為隊伍中有太多男生,露比最多只願意幫忙加油總共$k$次,不然他就會暈倒。
為了讓露比覺得幫助你有意義,她現在請你先算出有幾種方式可以打倒魔王。

註:一次挑戰中不一定所有人都要發動攻擊,露比也不一定要加油到剛好$k$次。


Input Format

輸入的第一行包含三個整數$n$, $k$ 以及 $S$ $(1 \le n \le 25, 0 \le k \le n, 1 \le S \le 10^ {16})$,代表人數、露比願意加油的次數以及魔王的血量。
輸入的第二行包含$n$個正整數$a_i$ $(1 \le a_i \le 10^ 9 )$,代表所有人的原始戰力。

Output Format

請輸出一行整數,代表有幾種方法可以打倒魔王

Sample Input

#輸入範例1:
3 1 1
1 1 1

#輸出範例2:
2 2 10
4 3

Sample Output

#輸出範例1
6

#輸出範例2
1

Hints

子任務(測資)額外限制分數
1(0~3)$k = 0, S \le 10^ 6, n \le 23 $10
2(4~7)$k = 0, n \le 23$20
3(8~11)$n \le 13 $20
4(12~19)50

輸入範例1中,共有六種可能的方式可以打倒魔王。
1. 由一號勇者發動攻擊
2. 由受露比加油後的一號勇者發動攻擊
1. 由二號勇者發動攻擊
2. 由受露比加油後的二號勇者發動攻擊
5. 由三號勇者發動攻擊
6. 由受露比加油後的三號勇者發動攻擊

輸入範例2中,共有一種可能的方式可以打倒魔王。
1. 由一號及受露比加油後的二號勇者發動攻擊

Problem Source

problem set by oToToT
adapted from Codeforces 525E

Subtasks

For Testdata: 0 ~ 3, Score: 10
For Testdata: 4 ~ 7, Score: 20
For Testdata: 8 ~ 11, Score: 20
For Testdata: 12 ~ 19, Score: 50
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 262144 65536
1 1000 262144 65536
2 1000 262144 65536
3 1000 262144 65536
4 1000 262144 65536
5 1000 262144 65536
6 1000 262144 65536
7 1000 262144 65536
8 1000 262144 65536
9 1000 262144 65536
10 1000 262144 65536
11 1000 262144 65536
12 1000 262144 65536
13 1000 262144 65536
14 1000 262144 65536
15 1000 262144 65536
16 1000 262144 65536
17 1000 262144 65536
18 1000 262144 65536
19 1000 262144 65536