Greg has a pad. The pad's screen is an n × m rectangle, each cell can be either black or white. We'll consider the pad rows to be numbered with integers from 1 to n from top to bottom. Similarly, the pad's columns are numbered with integers from 1 to m from left to right.

Greg thinks that the pad's screen displays a cave if the following conditions hold:

  * There is a segment [l, r] (1 ≤ l ≤ r ≤ n), such that each of the rows l, l + 1, ..., r has exactly two black cells and all other rows have only white cells. 
  * There is a row number t (l ≤ t ≤ r), such that for all pairs of rows with numbers i and j (l ≤ i ≤ j ≤ t) the set of columns between the black cells in row i (with the columns where is these black cells) is the subset of the set of columns between the black cells in row j (with the columns where is these black cells). Similarly, for all pairs of rows with numbers i and j (t ≤ i ≤ j ≤ r) the set of columns between the black cells in row j (with the columns where is these black cells) is the subset of the set of columns between the black cells in row i (with the columns where is these black cells). 



Greg wondered, how many ways there are to paint a cave on his pad. Two ways can be considered distinct if there is a cell that has distinct colors on the two pictures.

Help Greg.

Input

The first line contains two integers n, m — the pad's screen size (1 ≤ n, m ≤ 2000).

Output

In the single line print the remainder after dividing the answer to the problem by 1000000007 (109 + 7).

Examples

Input

1 1


Output

0


Input

4 4


Output

485


Input

3 5


Output

451
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > st;
bool cmp(pair<int, int> A, pair<int, int> B) {
  return A.first + A.second * 2 > B.first + B.second * 2;
}
long long C[60][60], g[60][60], f[60][60];
void mul(long long &a, long long b) {
  a *= b;
  a %= 1000000007;
}
void deal() {
  for (int i = 0; i < 60; i++)
    for (int j = 0; j <= i; j++) {
      if (i == 0 || j == 0)
        C[i][j] = 1;
      else
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j], C[i][j] %= 1000000007;
    }
}
int main() {
  int N, K, a, A, B, t;
  deal();
  long long ansf, ansg;
  while (cin >> N >> K) {
    A = B = 0;
    for (int i = 0; i < N; i++) {
      scanf("%d", &a);
      if (a == 50)
        A++;
      else
        B++;
    }
    long long oo = 1LL << 62;
    for (int i = 0; i < 60; i++) {
      for (int j = 0; j < 60; j++) {
        f[i][j] = oo;
      }
    }
    memset(g, 0, sizeof(g));
    ansf = oo;
    ansg = 0;
    f[A][B] = 0;
    g[A][B] = 1;
    st.clear();
    for (int i = 0; i <= A; i++) {
      for (int j = 0; j <= B; j++) {
        st.push_back(pair<int, int>(i, j));
      }
    }
    sort(st.begin(), st.end(), cmp);
    int M = st.size();
    int a0, b0, a1, b1, a2, b2;
    for (t = 0; t < M; t++) {
      int i = st[t].first;
      int j = st[t].second;
      if (f[i][j] == oo) continue;
      if (i * 50 + j * 100 <= K) {
        if (ansf > f[i][j] + 1) {
          ansf = f[i][j] + 1;
          ansg = g[i][j];
        } else if (ansf == f[i][j] + 1) {
          ansg += g[i][j];
          ansg %= 1000000007;
        }
        continue;
      }
      for (a0 = 0; a0 <= i; a0++) {
        if (a0 * 50 <= K) {
          for (b0 = 0; b0 <= j; b0++) {
            if (a0 + b0 > 0 && a0 * 50 + b0 * 100 <= K) {
              int i1 = A - i + a0, j1 = B - j + b0;
              int tmps = a0 * 50 + b0 * 100;
              for (a1 = 0; a1 <= i1; a1++) {
                if (a1 * 50 < tmps) {
                  for (b1 = 0; b1 <= j1; b1++) {
                    if (a1 + b1 > 0 && a1 * 50 + b1 * 100 < tmps) {
                      int a2 = i - a0 + a1, b2 = j - b0 + b1;
                      long long tmpg = g[i][j];
                      mul(tmpg, C[i][a0]);
                      mul(tmpg, C[j][b0]);
                      mul(tmpg, C[i1][a1]);
                      mul(tmpg, C[j1][b1]);
                      if (f[a2][b2] > f[i][j] + 2) {
                        f[a2][b2] = f[i][j] + 2;
                        g[a2][b2] = tmpg;
                      } else if (f[a2][b2] == f[i][j] + 2) {
                        g[a2][b2] += tmpg;
                        g[a2][b2] %= 1000000007;
                      }
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
    if (ansf == oo)
      cout << "-1" << endl;
    else
      cout << ansf << endl;
    cout << ansg << endl;
  }
}
