和 / sum

时间限制:3.00s
内存限制:256.00MB

题目描述

给你一个长度为n的序列 $a_1,a_2,…a_n$，你可以从中挑选一些数，并且对于挑选出来的这些数，你可以选至多k个数施加魔法，对一个数x施加魔法，则会让x变成x!（阶乘），问有多少种不同的方案使得选出的数的和为S。

认为两种方案相同当且仅当选出和施加魔法的数在原数列中的下标相同。

输入格式

第一行是三个正整数n，k，S，分别表示数列的长度、至多可以施加魔法的次数和要求的和。

接下来一行n个整数a_1,a_2,…a_n。

输出格式

一个整数，表示方案数。

输入输出样例

样例1 输入

3 1 1
1 1 1

样例1 输出

6

样例2 输入

2 2 7
4 3

样例2 输出

1

测试点数据范围

#1 - #3:1≤k≤n≤17,0≤a_i≤S≤1e7;

#4 - #6:1≤k≤n≤17,0≤a_i≤S≤10^{15};

#7 - #8:1≤k≤n≤26,0≤a_i≤S≤10^7;

#9 - #10:1≤k≤n≤17,0≤a_i≤S≤10^{15}