I have a lot of friends. Every friend is very small.
I often go out with my friends. Put some friends in your backpack and go out together.
Every morning I decide which friends to go out with that day. Put friends one by one in an empty backpack.
I'm not very strong. Therefore, there is a limit to the weight of friends that can be carried at the same time.
I keep friends so that I don't exceed the weight limit. The order in which you put them in depends on your mood.
I won't stop as long as I still have friends to put in. I will never stop.


…… By the way, how many patterns are there in total for the combination of friends in the backpack?



Input

N W
w1
w2
..
..
..
wn


On the first line of input, the integer N (1 ≤ N ≤ 200) and the integer W (1 ≤ W ≤ 10,000) are written in this order, separated by blanks. The integer N represents the number of friends, and the integer W represents the limit of the weight that can be carried at the same time. It cannot be carried if the total weight is greater than W.

The next N lines contain an integer that represents the weight of the friend. The integer wi (1 ≤ wi ≤ 10,000) represents the weight of the i-th friend.

Output

How many possible combinations of friends are finally in the backpack? Divide the total number by 1,000,000,007 and output the remainder. Note that 1,000,000,007 are prime numbers.

Note that "no one is in the backpack" is counted as one.

Examples

Input

4 8
1
2
7
9


Output

2


Input

4 25
20
15
20
15


Output

4


Input

6 37
5
9
13
18
26
33


Output

6
#include <bits/stdc++.h>
using namespace std;
template <class InIt1, class InIt2>
int partial_compare(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2) {
  return lexicographical_compare(first1, last1, first2, last2)   ? -1
         : lexicographical_compare(first2, last2, first1, last1) ? 1
                                                                 : 0;
}
template <class InIt, class T>
inline int index_of(InIt first1, InIt last1, const T &val) {
  InIt f = find(first1, last1, val);
  return f != last1 ? distance(f, first1) : -1;
}
template <class InIt, class T>
inline int bindex_of(InIt first1, InIt last1, const T &val) {
  auto it = lower_bound(first1, last1, val);
  if (it == last1) {
    return ~distance(it, first1);
  } else if (*it == val) {
    return distance(it, first1);
  } else
    return ~distance(it, first1);
}
vector<int> iotav(int begin, int end) {
  vector<int> r(end - begin);
  iota(r.begin(), r.end(), begin);
  return r;
}
struct iotait {
  int n;
  iotait(int n = 0) : n(n) {}
  iotait &operator++() {
    ++n;
    return *this;
  }
  int operator*() { return n; }
};
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
void exgcd(long long a, long long b, long long &x, long long &y) {
  if (b != 0) {
    exgcd(b, a % b, y, x);
    y -= a / b * x;
  } else {
    x = 1;
    y = 0;
  }
}
template <class T = int, class TParentFunc = const T &(*)(const T &, const T &)>
struct SegTree {
  int count;
  vector<T> tree;
  TParentFunc parent;
  SegTree(int size, TParentFunc parentBuilder = std::min,
          T initialFill = 1000000000)
      : count((size | size - 1) + 1), tree(count * 2), parent(parentBuilder) {
    fill(tree.begin() + (count), tree.begin() + (count) + (count), initialFill);
    rebuild();
  }
  T &operator[](int i) { return tree[i + count]; }
  void rebuild() {
    for (int i = (count)-1; i >= 0; i--) {
      tree[i] = parent(tree[i * 2], tree[i * 2 + 1]);
    }
  }
  void update(int index, T value) {
    tree[index + count] = value;
    for (int i = (index + count) / 2; i > 0; i /= 2)
      tree[i] = parent(tree[i * 2], tree[i * 2 + 1]);
  }
  T query(int s, int e, int i, int l, int r, T value) {
    if (r <= s || e <= l) return value;
    if (s <= l && r <= e) return parent(value, tree[i]);
    value = query(s, e, i * 2, l, (l + r) / 2, value);
    value = query(s, e, i * 2 + 1, (l + r) / 2, r, value);
    return value;
  }
  T query(int start, int count, T initialValue) {
    return query(start, start + count, 1, 0, count, initialValue);
  }
};
vector<unsigned char> isPrime;
vector<int> primes;
void initPrimes(int n) {
  isPrime = vector<unsigned char>(n + 1, true);
  isPrime[0] = isPrime[1] = false;
  for (int i = (2); i < (n + 1); i++) {
    if (!isPrime[i]) continue;
    primes.push_back(i);
    for (int j = i * 2; j <= n; j += i) isPrime[j] = false;
  }
}
vector<vector<double>> makePascalTriangle(int n, bool probability = false) {
  vector<vector<double>> t;
  if (!t.size()) {
    t.push_back(vector<double>(1, 1));
  }
  for (int i = (t.size()); i < (n + 1); i++) {
    t.push_back(vector<double>(i + 1));
    for (int j = 0; j < (i); j++) {
      double x = t[i - 1][j] * (probability ? 0.5 : 1);
      t[i][j] += x;
      t[i][j + 1] += x;
    }
  }
  return t;
}
struct P3 {
  double x, y, z;
  P3(double x = 0, double y = 0, double z = 0) : x(x), y(y), z(z) {}
  P3 operator+() const { return *this; }
  P3 operator+(const P3 &_) const { return P3(x + _.x, y + _.y, z + _.z); }
  P3 operator-() const { return P3(-x, -y, -z); }
  P3 operator-(const P3 &_) const { return *this + -_; }
  P3 operator*(double _) const { return P3(x * _, y * _, z * _); }
  P3 operator/(double _) const { return P3(x / _, y / _, z / _); }
  double dot(const P3 &_) const { return x * _.x + y * _.y + z * _.z; }
  P3 cross(const P3 &_) const {
    return P3(y * _.z - z * _.y, z * _.x - x * _.z, x * _.y - y * _.x);
  }
  double sqlength() const { return x * x + y * y + z * z; }
  double length() const { return sqrt(sqlength()); }
  P3 direction() const { return *this / length(); }
};
inline istream &operator>>(istream &in, P3 &p) {
  in >> p.x >> p.y >> p.z;
  return in;
}
inline double abs(P3 p) { return p.length(); }
struct Sphere {
  P3 c;
  double r;
  Sphere(double x, double y, double z, double r) : c(x, y, z), r(r) {}
  Sphere(P3 c, double r) : c(c), r(r) {}
  bool IntersectWith(const Sphere &rhs) const {
    return abs(c - rhs.c) - (r + rhs.r) < 1e-10;
  }
};
inline istream &operator>>(istream &in, Sphere &c) {
  in >> c.c >> c.r;
  return in;
}
struct P2 {
  double x, y;
  P2(double x = 0, double y = 0) : x(x), y(y) {}
  P2(complex<double> c) : x(c.real()), y(c.imag()) {}
  P2 operator+() const { return *this; }
  P2 operator+(const P2 &_) const { return P2(x + _.x, y + _.y); }
  P2 operator-() const { return P2(-x, -y); }
  P2 operator-(const P2 &_) const { return *this + -_; }
  P2 operator*(double _) const { return P2(x * _, y * _); }
  P2 operator/(double _) const { return P2(x / _, y / _); }
  double dot(const P2 &_) const { return x * _.x + y * _.y; }
  double cross(const P2 &_) const { return x * _.y - y * _.x; }
  double sqlength() const { return x * x + y * y; }
  double length() const { return sqrt(sqlength()); }
  P2 orthogonal() const { return P2(y, -x); }
  P2 direction() const { return *this / length(); }
};
inline istream &operator>>(istream &in, P2 &p) {
  in >> p.x >> p.y;
  return in;
}
inline double abs(P2 p2) { return p2.length(); }
inline P2 orthogonal(P2 p) { return p.orthogonal(); }
inline complex<double> orthogonal(complex<double> c) {
  return c * complex<double>(0, 1);
}
inline pair<P2, P2> get_same_distance_points(P2 a, P2 b, double d) {
  assert(abs(a - b) <= 2 * d + 1e-10);
  auto v = (a + b) / 2.0 - a;
  auto vl = abs(v);
  auto wl = sqrt(d * d - vl * vl);
  auto w = orthogonal(v) * (wl / vl);
  return make_pair(a + v + w, a + v - w);
}
struct Circle {
  P2 c;
  double r;
  Circle(double x, double y, double r) : c(x, y), r(r) {}
  Circle(P2 c, double r) : c(c), r(r) {}
  bool IntersectWith(const Circle &rhs) const {
    return abs(c - rhs.c) - (r + rhs.r) < 1e-10;
  }
  bool Contains(const P2 &p) const { return abs(p - c) - r < 1e-10; }
};
inline istream &operator>>(istream &in, Circle &c) {
  in >> c.c >> c.r;
  return in;
}
inline int next_bit_permutation(int x) {
  int t = x | (x - 1);
  return (t + 1) | (unsigned)((~t & -~t) - 1) >> (__builtin_ctz(x) + 1);
}
template <class T>
int bit_swap(T x, size_t p1, size_t p2, size_t len) {
  T mask = (1ul << len) - 1;
  T ope = (x >> p1 ^ x >> p2) & mask;
  return x ^ (ope << p1 | ope << p2);
}
struct Path {
  int from;
  int to;
  double cost;
  double capacity;
  Path(int from = 0, int to = 0, double cost = 0, double capacity = -1)
      : from(from), to(to), cost(cost), capacity(capacity) {}
  bool operator<(const Path &rhs) const { return cost < rhs.cost; }
  bool operator>(const Path &rhs) const { return cost > rhs.cost; }
};
pair<double, vector<int>> prim(const vector<vector<double>> &costTable) {
  int N = costTable.size();
  priority_queue<Path, vector<Path>, greater<Path>> q;
  q.push(Path(0, 0, 0));
  vector<int> parent(N, -1);
  double totalCost = 0;
  while (!q.empty()) {
    Path cur = q.top();
    q.pop();
    int i = cur.to;
    if (parent[i] != -1) continue;
    parent[i] = cur.from;
    totalCost += cur.cost;
    for (int j = 0; j < (N); j++)
      if (parent[j] == -1) q.push(Path(i, j, costTable[i][j]));
  }
  return make_pair(totalCost, parent);
}
pair<vector<double>, vector<int>> dijkstra(const vector<vector<Path>> &routes,
                                           int start = 0, int goal = -1) {
  int N = routes.size();
  priority_queue<Path, vector<Path>, greater<Path>> q;
  q.push(Path(start, start, 0));
  vector<int> prev(N, -1);
  vector<double> cost(N, 1000000000);
  while (!q.empty()) {
    Path cur = q.top();
    q.pop();
    int i = cur.to;
    if (prev[i] != -1) continue;
    prev[i] = cur.from;
    cost[i] = cur.cost;
    if (i == goal) {
      break;
    }
    for (int j = 0; j < (routes[i].size()); j++) {
      Path next = Path(i, routes[i][j].to, cur.cost + routes[i][j].cost);
      if (prev[next.to] == -1) q.push(next);
    }
  }
  return make_pair(cost, prev);
}
template <class T>
struct Die {
  T v[6];
  void rt(int x, int y, int z, int w) {
    swap(v[x], v[y]);
    swap(v[x], v[z]);
    swap(v[x], v[w]);
  }
  void rotateLeft() { rt(0, 4, 5, 1); }
  void rotateRight() { rt(1, 5, 4, 0); }
  void rotateDown() { rt(0, 3, 5, 2); }
  void rotateUp() { rt(2, 5, 3, 0); }
  void rotateCw() { rt(3, 1, 2, 4); }
  void rotateCcw() { rt(4, 2, 1, 3); }
  bool operator<(const Die &rhs) const {
    return lexicographical_compare(v, (sizeof(v) / sizeof(v[0])), rhs.v,
                                   (sizeof(rhs.v) / sizeof(rhs.v[0])));
  }
  bool operator==(const Die &rhs) const {
    return equal(v, (sizeof(v) / sizeof(v[0])), rhs.v);
  }
  bool operator!=(const Die &rhs) const {
    return !equal(v, (sizeof(v) / sizeof(v[0])), rhs.v);
  }
};
template <class T>
struct Octahedra {
  T v[8];
  void rt(int x, int y, int z, int w) {
    swap(v[x], v[y]);
    swap(v[x], v[z]);
    swap(v[x], v[w]);
  }
  void rotateLeft() {
    rt(0, 1, 2, 3);
    rt(4, 5, 6, 7);
  }
  void rotateRight() {
    rt(3, 2, 1, 0);
    rt(7, 6, 5, 4);
  }
  void rotateDown() {
    rt(0, 4, 7, 3);
    rt(1, 5, 6, 2);
  }
  void rotateUp() {
    rt(3, 7, 4, 0);
    rt(2, 6, 5, 2);
  }
  void rotateCw() {
    rt(0, 1, 5, 4);
    rt(3, 2, 6, 7);
  }
  void rotateCcw() {
    rt(4, 5, 1, 0);
    rt(7, 6, 1, 3);
  }
  bool operator<(const Octahedra &rhs) const {
    return lexicographical_compare(v, (sizeof(v) / sizeof(v[0])), rhs.v,
                                   (sizeof(rhs.v) / sizeof(rhs.v[0])));
  }
  bool operator==(const Octahedra &rhs) const {
    return equal(v, (sizeof(v) / sizeof(v[0])), rhs.v);
  }
  bool operator!=(const Octahedra &rhs) const {
    return !equal(v, (sizeof(v) / sizeof(v[0])), rhs.v);
  }
};
template <class T>
class vevector : public vector<vector<T>> {
 public:
  vevector(int n = 0, int m = 0) : vector<vector<T>>(n, vector<T>(m)){};
  vevector(int n, int m, const T &initial)
      : vector<vector<T>>(n, vector<T>(m, initial)){};
};
template <class T>
T read() {
  T t;
  cin >> t;
  return t;
}
template <class T>
vector<T> read(int n) {
  vector<T> v;
  for (int i = 0; i < (n); i++) {
    v.push_back(read<T>());
  }
  return v;
}
template <class T>
vevector<T> read(int n, int m) {
  vevector<T> v;
  for (int i = 0; i < (n); i++) v.push_back(read<T>(m));
  return v;
}
template <class T>
vevector<T> readjag(int n) {
  vevector<T> v;
  for (int i = 0; i < (n); i++) v.push_back(read<T>(read<int>()));
  return v;
}
struct _Reader {
  template <class T>
  _Reader operator,(T &rhs) {
    cin >> rhs;
    return *this;
  }
};
template <class T>
void write(const T &t) {
  cout << t << endl;
}
template <class T, class T2>
void write(const T &t, const T2 &t2) {
  cout << t << ' ' << t2 << endl;
}
template <class T>
void write(const vector<T> &v) {
  ostringstream ss;
  for (auto x : v) ss << x << ' ';
  auto s = ss.str();
  cout << s.substr(0, s.length() - 1) << endl;
}
void solve();
int main() {
  solve();
  return 0;
}
int dfs(const vector<int> &we, const vector<int> &wsum,
        vector<vevector<int>> &memo, int cur, int weight, int weLastSkiped,
        vector<int> &dbg) {
  if (cur == -1) {
    if (weight >= we[weLastSkiped]) {
      return 0;
    }
    return 1;
  }
  if (memo[cur][weight][weLastSkiped] != -1) {
    return memo[cur][weight][weLastSkiped];
  }
  if (we[weLastSkiped] + wsum[cur] <= weight) {
    memo[cur][weight][weLastSkiped] = 0;
    return 0;
  }
  int pat = 0;
  if (weight >= we[cur]) {
    dbg.push_back(we[cur]);
    pat += dfs(we, wsum, memo, cur - 1, weight - we[cur], weLastSkiped, dbg);
    dbg.pop_back();
  }
  { pat += dfs(we, wsum, memo, cur - 1, weight, cur, dbg); }
  return memo[cur][weight][weLastSkiped] = pat % 1000000007;
}
void solve() {
  auto testcases = 1000000000;
  for (int testcase = 0; testcase < (testcases); testcase++) {
    int n, w;
    _Reader(), n, w;
    auto we = read<int>(n);
    we.push_back(1000000000);
    n++;
    sort(we.begin(), we.end());
    auto wesum = vector<int>();
    partial_sum(we.begin(), we.end(), back_inserter(wesum));
    vector<vevector<int>> memo(n + 1, vevector<int>(w + 1, n + 1, -1));
    auto dbg = vector<int>();
    int ret = dfs(we, wesum, memo, n - 2, w, n - 1, dbg);
    write(ret);
    break;
  }
}
