AOJ2333.cpp

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

vector<int> w, sum;
int memo[256][16384];

int dp(int N, int W) {
  if (N == 0) return 1;
  if (sum[N-1] <= W) return 1;
  if (memo[N][W] >= 0) return memo[N][W];
  int res = dp(N - 1, W);
  if (w[N-1] <= W) res += dp(N - 1, W - w[N-1]);
  return memo[N][W] = res % 1000000007;
}

int main() {
  REP(i,256) REP(j,16384) memo[i][j] = -1;
  int N, W;
  cin >> N >> W;
  w.assign(N, 0); sum.assign(N, 0);
  REP(i,N) cin >> w[i];
  sort(ALL(w));
  sum[0] = w[0];
  REP(i,N-1) sum[i+1] = sum[i] + w[i+1];
  cout << dp(N, W) << endl;
  return 0;
}