問題文

典型商店には N 個の区別できる品物があります。品物には 1, 2, \cdots, N と番号が付けられており、品物 i の値段は A_i 円です。

あなたは商店に売られている品物からちょうど K 個を選んで、値段の合計が P 円以下となるように買い物をしたいです。あり得る品物の選び方は何通りあるでしょうか？

なお、2 通りの品物の選び方は、ある品物 i があって、品物 i が一方では選ばれており他方では選ばれていないときに区別されます。

制約

• 1 \leq K \leq N \leq 40
• 1 \leq P \leq 10^{18}
• 1 \leq A_i \leq 10^{16} (1 \leq i \leq N)
• 入力は全て整数

入力例 1

5 2 10
3 8 7 5 11

出力例 1

2

ちょうど 2 個を選び、値段の合計が 10 円以下となるような品物の選び方は、以下の 2 通りです。

• 品物 1 と品物 3 を選ぶ
• 品物 1 と品物 4 を選ぶ

入力例 2

5 1 10
7 7 7 7 7

出力例 2

5

品物は、同じ値段であったとしても区別されることに注意してください。

入力例 3

40 20 100
1 3 1 3 4 1 3 5 5 3 3 4 1 5 4 4 3 1 3 4 1 3 2 4 4 1 5 2 5 3 1 3 3 3 5 5 5 2 3 5

出力例 3

137846528820

答えが 32 bit 整数に収まらないことがあることに注意してください。