Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
798 B
2
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*b/__gcd(a,b)
const ll gde=1e9+7;
ll n,k,a[16],memo[16][7501][16];

ll dp(ll idx,ll sum,ll take){
  if(idx==0)return (sum<=k&&take==0);
  ll &sol=memo[idx][sum][take];
  if(sol!=-1)return sol;
  sol=(take+1)*dp(idx-1,sum,take)+dp(idx-1,sum+a[idx],take+1);
  if(take)sol+=take*dp(idx-1,sum-a[idx],take-1);
  sol%=gde;
  return sol;
}

void Input(){
  cin>>n>>k;
  for(int i=1;i<=n;i++)cin>>a[i];
}

void Solve(){
  sort(a+1,a+n+1);
  memset(memo,-1,sizeof(memo));
  cout<<dp(n,0,0)<<endl;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  Input();
  Solve();
}