// BEGIN CUT HERE

// END CUT HERE
#line 5 "AquaparkPuzzle.cpp"
#include <iostream>
#include <sstream>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <utility>
#include <numeric>
#include <functional>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define forl(i, n) for (int i = 1; i <= int(n); i++)
#define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define fore(i, l, r) for (int i = int(l); i <= int(r); i++)
#define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
#define all(a) (a).begin(), (a).end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
#define mp(x, y) make_pair((x), (y))
#define ft first
#define sc second
#define isnan(a) false
#define isinf(a) false

using namespace std;

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;

class AquaparkPuzzle
{
	public:
	int countSchedules(int k, int m, vector <int> c);
};

int gcd(int a, int b, int& x, int& y)
{
	if (a == 0)
	{
		x = 0, y = 1;
		return b;
	}

	int xx, yy, g = gcd(b % a, a, xx, yy);
	x = yy - b / a * xx;
	y = xx;
	return g;
}

const int mod = 1000 * 1000 * 1000 + 7;

int inv(int a)
{
	int x, y;
	assert(gcd(a, mod, x, y) == 1);
	x %= mod;
	(x < 0) && (x += mod);
	return x;
}

const int N = 11 + 3, K = 1000 * 1000 + 3, EXPN = (1 << 11) + 3, EXPN3 = 180000;

int pw[N], fact[K], ifact[K];
int g[EXPN], c[EXPN];

int get(int mask, int i) { return (mask / pw[i]) % 3; }
int _set(int mask, int i, int v) { return mask - (get(mask, i) - v) * pw[i]; }

int C(int n, int k)
{
	if (k < 0 || k > n) return 0;
	int ans = int((fact[n] * 1ll * ifact[k]) % mod);
	ans = int((ans * 1ll * ifact[n - k]) % mod);
	return ans;
}

int binPow(int a, int b)
{
	int ans = 1;
	while (b)
	{
		if (b & 1) ans = int((ans * 1ll * a) % mod);
		a = int((a * 1ll * a) % mod);
		b >>= 1;
	}
	return ans;
}

int n;

string get(int mask)
{
	string s;
	ford(i, n) s.pb(char('0' + get(mask, i)));
	return s;
}

int b[N];
int z[EXPN3][N];

int AquaparkPuzzle::countSchedules(int k, int m, vector <int> cost)
{
	pw[0] = 1; forl(i, N - 1) pw[i] = pw[i - 1] * 3;

	fact[0] = 1; forl(i, K - 1) fact[i] = int((fact[i - 1] * 1ll * i) % mod);
	forn(i, K) ifact[i] = inv(fact[i]);

	n = sz(cost);
	forn(mask, (1 << n))
	{
		int s = 0;
		forn(i, n) if (mask & (1 << i)) s += cost[i];
		g[mask] = s <= m;
	}

	forn(mask, (1 << n))
	{
		c[mask] = 0;
		forn(msk, (1 << n)) if (!(mask & msk)) c[mask] += g[msk];
	}

	memset(z, 0, sizeof(z)); 
	forn(mask, pw[n])
	{
		forn(i, n) b[i] = get(mask, i);
		int bmsk[3] = { 0 };
		forn(i, n) bmsk[b[i]] |= (1 << i);

		if (bmsk[1] == 0)
		{
			z[mask][0] = 1;
			continue;
		}

		int msk = bmsk[1] | bmsk[2];
		for (int cmsk = msk; cmsk > 0; cmsk = (cmsk - 1) & msk)
		{
			if ((cmsk & bmsk[1]) && g[cmsk])
			{
				int nmsk = mask;
				forn(i, n) if (b[i] == 1 && (cmsk & (1 << i))) nmsk -= pw[i];

				int* p1 = &z[mask][1];
				int* p2 = &z[nmsk][0];
				forl(i, n)
				{
					*p1 += *p2;
					(*p1 >= mod) && (*p1 -= mod);
					p1++, p2++;
					/*int& dv = z[mask][i];
					dv += z[nmsk][i - 1];
					(dv >= mod) && (dv -= mod);*/
				}
			}
		}
	}

	/*forn(mask, pw[n])
		forn(i, n + 1)
		{
			ford(j, n) cerr << get(mask, j);
			cerr << ' ' << i << ": " << z[mask][i] << endl;
		}*/

	int ans = 0;
	forn(mask, pw[n])
	{
		forn(i, n) b[i] = get(mask, i);
		int bmsk[3] = { 0 };
		forn(i, n) bmsk[b[i]] |= (1 << i);

		int sg = 1; forn(i, n) if (b[i] < 2) sg = -sg;

		int sum = 0;
		forn(i, n + 1)
		{
			int cnt = C(k, i);
			if (cnt == 0) continue;
			cnt = int((cnt * 1ll * z[mask][i]) % mod);
			cnt = int((cnt * 1ll * binPow(c[bmsk[0] | bmsk[1]], k - i)) % mod);
			sum += cnt;
			(sum >= mod) && (sum -= mod);
		}

		//cerr << get(mask) << ' ' << sum << ' ' << sg << endl;
		ans += sum * sg;
		(ans < 0) && (ans += mod);
		(ans >= mod) && (ans -= mod);
	}
	
	return ans;
}

// BEGIN CUT HERE
namespace moj_harness {
	int run_test_case(int);
	void run_test(int casenum = -1, bool quiet = false) {
		if (casenum != -1) {
			if (run_test_case(casenum) == -1 && !quiet) {
				cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
			}
			return;
		}
		
		int correct = 0, total = 0;
		for (int i=0;; ++i) {
			int x = run_test_case(i);
			if (x == -1) {
				if (i >= 100) break;
				continue;
			}
			correct += x;
			++total;
		}
		
		if (total == 0) {
			cerr << "No test cases run." << endl;
		} else if (correct < total) {
			cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
		} else {
			cerr << "All " << total << " tests passed!" << endl;
		}
	}
	
	int verify_case(int casenum, const int &expected, const int &received, clock_t elapsed) { 
		cerr << "Example " << casenum << "... "; 
		
		string verdict;
		vector<string> info;
		char buf[100];
		
		if (elapsed > CLOCKS_PER_SEC / 200) {
			sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
			info.push_back(buf);
		}
		
		if (expected == received) {
			verdict = "PASSED";
		} else {
			verdict = "FAILED";
		}
		
		cerr << verdict;
		if (!info.empty()) {
			cerr << " (";
			for (int i=0; i<(int)info.size(); ++i) {
				if (i > 0) cerr << ", ";
				cerr << info[i];
			}
			cerr << ")";
		}
		cerr << endl;
		
		if (verdict == "FAILED") {
			cerr << "    Expected: " << expected << endl; 
			cerr << "    Received: " << received << endl; 
		}
		
		return verdict == "PASSED";
	}

	int run_test_case(int casenum) {
		switch (casenum) {
		case 0: {
			int k                     = 3;
			int m                     = 3;
			int c[]                   = {1, 2};
			int expected__            = 16;

			clock_t start__           = clock();
			int received__            = AquaparkPuzzle().countSchedules(k, m, vector <int>(c, c + (sizeof c / sizeof c[0])));
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 1: {
			int k                     = 3;
			int m                     = 3;
			int c[]                   = {2, 2};
			int expected__            = 0;

			clock_t start__           = clock();
			int received__            = AquaparkPuzzle().countSchedules(k, m, vector <int>(c, c + (sizeof c / sizeof c[0])));
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 2: {
			int k                     = 4;
			int m                     = 3;
			int c[]                   = {1, 2, 2};
			int expected__            = 66;

			clock_t start__           = clock();
			int received__            = AquaparkPuzzle().countSchedules(k, m, vector <int>(c, c + (sizeof c / sizeof c[0])));
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 3: {
			int k                     = 6;
			int m                     = 7;
			int c[]                   = {2, 3, 4, 7};
			int expected__            = 4800;

			clock_t start__           = clock();
			int received__            = AquaparkPuzzle().countSchedules(k, m, vector <int>(c, c + (sizeof c / sizeof c[0])));
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 4: {
			int k                     = 1000;
			int m                     = 20;
			int c[]                   = {8, 2, 13, 18, 7, 3};
			int expected__            = 15681195;

			clock_t start__           = clock();
			int received__            = AquaparkPuzzle().countSchedules(k, m, vector <int>(c, c + (sizeof c / sizeof c[0])));
			return verify_case(casenum, expected__, received__, clock()-start__);
		}

		// custom cases

        case 5: {
			int k                     = 1000000;
			int m                     = 1000;
			int c[]                   = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
			int expected__            = 5069980;

			clock_t start__           = clock();
			int received__            = AquaparkPuzzle().countSchedules(k, m, vector <int>(c, c + (sizeof c / sizeof c[0])));
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
/*      case 6: {
			int k                     = ;
			int m                     = ;
			int c[]                   = ;
			int expected__            = ;

			clock_t start__           = clock();
			int received__            = AquaparkPuzzle().countSchedules(k, m, vector <int>(c, c + (sizeof c / sizeof c[0])));
			return verify_case(casenum, expected__, received__, clock()-start__);
		}*/
/*      case 7: {
			int k                     = ;
			int m                     = ;
			int c[]                   = ;
			int expected__            = ;

			clock_t start__           = clock();
			int received__            = AquaparkPuzzle().countSchedules(k, m, vector <int>(c, c + (sizeof c / sizeof c[0])));
			return verify_case(casenum, expected__, received__, clock()-start__);
		}*/
		default:
			return -1;
		}
	}
}
 

int main(int argc, char *argv[]) {
	if (argc == 1) {
		moj_harness::run_test();
	} else {
		for (int i=1; i<argc; ++i)
			moj_harness::run_test(atoi(argv[i]));
	}
}
// END CUT HERE