Migrated from Lutece 2254 一切的开始,世界树的测验

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

"孩子， 当你出生的时候，整个搜索森林都在呼唤你的名字。" "孩子， 总有一天， 我的生命将抵达终点， 而你，将爆搜为王"

年轻的阿尔搜斯脑海里浮现起父亲的话,而今天,他18岁,在古老的世界树前,他需要利用自己搜索,剪枝的力量,解决世界树给出的难题,向所有人证明,他已经具备了成为搜索kingdom下一任国王的资格

要来了!世界树面前浮现出来n个月亮井,每个井中浮现出一个数字,大先知低声告诉阿尔搜斯,他需要从这n个数字中选出若干个数,他可以用圣光改变其中最多k个,从而让选出的数字和为世界树给出的一个数字S 阿尔搜斯的圣光可以让一个数X变为$\sum_{i=1}^X$

例如,他的圣光可以让100变为5050,让10变为55 现在他需要告诉世界树有多少种符合要求的方案数

阿尔搜斯天资聪颖,当然轻易通过了测试,现在,他带着问题找到了你--他的谋士,想看看你是否有跟随在他身边的资格

Input

输入第一行包含三个整数n,k,s.含义如上 第二行包含n个正整数$a_i$,表示每个月亮井中的数字

Output

输出有多少种选出的数字经若干圣光照耀后和为S的方案

Samples

5 0 3
1 1 1 1 1

10

5 2 10
1 2 3 4 5

9

Constraints

$1 ≤ n ≤ 25, 0 ≤ k ≤ n, 1 ≤ S ≤ 10^{16}$ $1 \leq a_i \leq 1000000$

Resources

2019 UESTC ACM Training for Search Algorithm and String