#define _CRT_SECURE_NO_WARNINGS #include "bits/stdc++.h" #pragma comment (linker, "/STACK:526000000") using namespace std; typedef string::const_iterator State; #define eps 1e-11L #define MAX_MOD 1000000007LL #define GYAKU 500000004LL #define MOD 998244353LL #define seg_size 262144*2LL #define pb push_back #define mp make_pair typedef long long ll; #define REP(a,b) for(long long (a) = 0;(a) < (b);++(a)) #define ALL(x) (x).begin(),(x).end() unsigned long xor128() { static unsigned long x = 123456789, y = 362436069, z = 521288629, w = time(NULL); unsigned long t = (x ^ (x << 11)); x = y; y = z; z = w; return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))); } void init() { iostream::sync_with_stdio(false); cout << fixed << setprecision(10); } #define int ll int powing(int now, int hoge) { int ans = 1; while (hoge) { if (hoge % 2) { ans *= now; ans %= MAX_MOD; } now *= now; now %= MAX_MOD; hoge /= 2LL; } return ans; } int inv(int now) { return powing(now, MAX_MOD - 2LL); } int going[1000]; vector mult(vector a, vector b) { vector ans; REP(i, 2) { REP(q, 2) { ans.push_back(0); REP(j, 2) { ans.back() += (a[i*2 + j] * b[q + 2 * j]) % MAX_MOD; ans.back() %= MAX_MOD; } ans.back() %= MAX_MOD; } } return ans; } int solve(int a, int b,int c) { vector inputs; inputs.push_back(a); inputs.push_back(b); inputs.push_back(1); inputs.push_back(0); vector gogo{ 1,0,0,1 }; c--; while (c) { if (c % 2) { gogo = mult(gogo, inputs); } inputs = mult(inputs, inputs); c /= 2; } return (gogo[0] * a + gogo[1]) % MAX_MOD; } void solve() { int n, w, k; cin >> n >> w >> k; vector inputs; REP(i, n) { int a; cin >> a; inputs.push_back(a); } going[0] = 1; for (int i = 0; i < 2 * w; ++i) { if (i == w) continue; REP(q, inputs.size()) { going[i + inputs[q]] += going[i]; going[i + inputs[q]] %= MAX_MOD; } } cout << solve(going[w], going[2 * w], k) << endl; } #undef int int main() { init(); solve(); }