Problem: If you have gone that far, you'll probably skip unnecessary legends anyway...

You are given a binary string <image> and an integer <image>. Find the number of integers k, 0 ≤ k < N, such that for all i = 0, 1, ..., m - 1

<image> Print the answer modulo 109 + 7.

Input

In the first line of input there is a string s consisting of 0's and 1's (1 ≤ |s| ≤ 40).

In the next line of input there is an integer n (1 ≤ n ≤ 5·105).

Each of the next n lines contains two space-separated integers pi, αi (1 ≤ pi, αi ≤ 109, pi is prime). All pi are distinct.

Output

A single integer — the answer to the problem.

Examples

Input

1
2
2 1
3 1


Output

2


Input

01
2
3 2
5 1


Output

15


Input

1011
1
3 1000000000


Output

411979884

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
using namespace std;
inline void Add(int &a, int b) {
  a += b;
  a >= 1000000007 ? a -= 1000000007 : 1;
}
inline int mul(int a, int b) { return 1ll * a * b % 1000000007; }
inline int add(int a, int b) {
  a += b;
  return a >= 1000000007 ? a - 1000000007 : a;
}
int ksm(int a, int b) {
  int ans = 1;
  for (; b; b >>= 1, a = mul(a, a))
    if (b & 1) ans = mul(ans, a);
  return ans;
}
map<long long, long long> bok, lst;
vector<long long> uz;
int p[99], tot = 0;
char sss[123];
int pa[1 << 20], tp = 0;
long long W(int l, int r) { return ((1ll << (r - l + 1)) - 1) << l; }
long long s0 = 0, all;
int m;
void D(int p) {
  lst.clear();
  for (auto it : bok) {
    long long ano = W(m - p + 1, p) & it.first;
    lst[(1ll * __builtin_popcountll(ano) << 45) + (it.first ^ ano)] +=
        it.second;
  }
  bok.clear();
  uz.clear();
  for (int i = 1; i <= m - p; i++)
    if ((s0 >> i & 1) + (s0 >> (i + p) & 1) == 0)
      uz.push_back(all ^ (1ll << i) ^ (1ll << (i + p) ^ (63ll << 45)));
  int tot = p - (m - p), c1 = 0;
  for (int i = m - p + 1; i <= p; i++) c1 += (s0 >> i & 1);
  for (auto it : lst) {
    for (long long p : uz) bok[it.first & p] += it.second;
    if ((it.first >> 45) != tot)
      bok[it.first] += it.second * (tot - (it.first >> 45));
    if (it.first >> 45)
      bok[it.first - (1ll << 45)] += it.second * ((it.first >> 45) - c1);
  }
}
int f[2][123], pi = 1, cc1;
void ED() {
  int now = 0, nxt = 1;
  for (int i = 1; i <= tp; i++) {
    fill(f[nxt], f[nxt] + 50, 0);
    for (int j = cc1; j <= 40; j++) {
      Add(f[nxt][j], mul(pa[i] - j, f[now][j]));
      if (j > cc1) Add(f[nxt][j - 1], mul(j - cc1, f[now][j]));
    }
    now ^= 1, nxt ^= 1;
  }
  printf("%d\n", mul(f[now][cc1], pi));
  exit(0);
}
int main() {
  int qaq;
  scanf("%s%d", sss + 1, &qaq);
  m = strlen(sss + 1);
  for (int i = 1; i <= m; i++)
    if (sss[i] == '1') s0 |= (1ll << i);
  cc1 = __builtin_popcountll(s0);
  int d29 = 0, d31 = 0, d37 = 0, d23 = 0;
  for (int i = 1, x, y; i <= qaq; i++) {
    scanf("%d%d", &x, &y);
    pi = mul(pi, ksm(x, y - 1));
    if (x == 23 && x < m)
      d23 = 1;
    else if (x == 29 && x < m)
      d29 = 1;
    else if (x == 31 && x < m)
      d31 = 1;
    else if (x == 37 && x < m)
      d37 = 1;
    else if (x >= m)
      pa[++tp] = x;
    else
      p[tot++] = x;
  }
  all = W(1, m);
  bok[all] = 1;
  sort(p, p + tot);
  if (__builtin_popcountll(s0) == 0 && d23 &&
      ((tot == 6 && p[0] == 5) || (tot == 5 && p[0] == 7))) {
    if (m == 40 && p[0] != 5 && d29 == 0 && d31 == 0 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 0, f[0][16] = 0, f[0][17] = 0, f[0][18] = 0, f[0][19] = 278,
      f[0][20] = 9293, f[0][21] = 87514, f[0][22] = 418248, f[0][23] = 1154848,
      f[0][24] = 1946434, f[0][25] = 2011334, f[0][26] = 1253454,
      f[0][27] = 454422, f[0][28] = 90226, f[0][29] = 9756, f[0][30] = 594,
      f[0][31] = 28, f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0,
      f[0][36] = 0, f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0,
      ED();
    }
    if (m == 40 && p[0] != 5 && d29 == 0 && d31 == 0 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 0, f[0][16] = 0, f[0][17] = 0, f[0][18] = 6623,
      f[0][19] = 220744, f[0][20] = 2177404, f[0][21] = 11041376,
      f[0][22] = 33136852, f[0][23] = 62360784, f[0][24] = 74566960,
      f[0][25] = 56355008, f[0][26] = 26452918, f[0][27] = 7479440,
      f[0][28] = 1227446, f[0][29] = 115570, f[0][30] = 6496, f[0][31] = 252,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 40 && p[0] != 5 && d29 == 0 && d31 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 0, f[0][16] = 0, f[0][17] = 246, f[0][18] = 19065,
      f[0][19] = 336170, f[0][20] = 2603300, f[0][21] = 11394248,
      f[0][22] = 30942912, f[0][23] = 54028546, f[0][24] = 60954272,
      f[0][25] = 43992530, f[0][26] = 19885780, f[0][27] = 5431364,
      f[0][28] = 858918, f[0][29] = 77594, f[0][30] = 4202, f[0][31] = 152,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 40 && p[0] != 5 && d29 == 0 && d31 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 0, f[0][16] = 5163, f[0][17] = 404024, f[0][18] = 7528860,
      f[0][19] = 62318924, f[0][20] = 293932262, f[0][21] = 872456808,
      f[0][22] = 698323525, f[0][23] = 193992806, f[0][24] = 876277367,
      f[0][25] = 50377861, f[0][26] = 377290990, f[0][27] = 84361576,
      f[0][28] = 11358400, f[0][29] = 909220, f[0][30] = 44874, f[0][31] = 1368,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 40 && p[0] != 5 && d29 && d31 == 0 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 0, f[0][16] = 0, f[0][17] = 392, f[0][18] = 24477,
      f[0][19] = 373756, f[0][20] = 2731632, f[0][21] = 11507898,
      f[0][22] = 30249270, f[0][23] = 51256820, f[0][24] = 56392210,
      f[0][25] = 39855894, f[0][26] = 17705862, f[0][27] = 4753036,
      f[0][28] = 736600, f[0][29] = 65030, f[0][30] = 3440, f[0][31] = 124,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 40 && p[0] != 5 && d29 && d31 == 0 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 0, f[0][16] = 8087, f[0][17] = 517510, f[0][18] = 8418000,
      f[0][19] = 65605474, f[0][20] = 297935076, f[0][21] = 857578000,
      f[0][22] = 623666977, f[0][23] = 47595474, f[0][24] = 715832303,
      f[0][25] = 944247514, f[0][26] = 333918330, f[0][27] = 73462050,
      f[0][28] = 9705572, f[0][29] = 760072, f[0][30] = 36734, f[0][31] = 1116,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 40 && p[0] != 5 && d29 && d31 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 138, f[0][16] = 28087, f[0][17] = 905664, f[0][18] = 11204926,
      f[0][19] = 74359108, f[0][20] = 301811376, f[0][21] = 798694444,
      f[0][22] = 415628691, f[0][23] = 693315009, f[0][24] = 359485047,
      f[0][25] = 722197034, f[0][26] = 247597354, f[0][27] = 52831450,
      f[0][28] = 6756022, f[0][29] = 510834, f[0][30] = 23786, f[0][31] = 680,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 40 && p[0] != 5 && d29 && d31 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 2419,
      f[0][15] = 517430, f[0][16] = 17911010, f[0][17] = 239726696,
      f[0][18] = 721479799, f[0][19] = 608503767, f[0][20] = 145468590,
      f[0][21] = 809524021, f[0][22] = 626443107, f[0][23] = 849620935,
      f[0][24] = 728231867, f[0][25] = 380346897, f[0][26] = 352306510,
      f[0][27] = 784464202, f[0][28] = 87224860, f[0][29] = 5908042,
      f[0][30] = 249868, f[0][31] = 6120, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 40 && p[0] == 5 && d29 == 0 && d31 == 0 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 246, f[0][14] = 6269,
      f[0][15] = 70380, f[0][16] = 474134, f[0][17] = 1997304,
      f[0][18] = 5366588, f[0][19] = 9157172, f[0][20] = 9922540,
      f[0][21] = 6727466, f[0][22] = 2752528, f[0][23] = 631924,
      f[0][24] = 71988, f[0][25] = 3550, f[0][26] = 56, f[0][27] = 0,
      f[0][28] = 0, f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0,
      f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0,
      f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 40 && p[0] == 5 && d29 == 0 && d31 == 0 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 3559, f[0][13] = 103560,
      f[0][14] = 1296282, f[0][15] = 9593496, f[0][16] = 45020070,
      f[0][17] = 137527508, f[0][18] = 274954408, f[0][19] = 360420286,
      f[0][20] = 308370698, f[0][21] = 169024174, f[0][22] = 57149494,
      f[0][23] = 11114942, f[0][24] = 1110766, f[0][25] = 49414, f[0][26] = 708,
      f[0][27] = 0, f[0][28] = 0, f[0][29] = 0, f[0][30] = 0, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 40 && p[0] == 5 && d29 == 0 && d31 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 76, f[0][12] = 7345, f[0][13] = 148232,
      f[0][14] = 1565668, f[0][15] = 10340564, f[0][16] = 44512582,
      f[0][17] = 126866036, f[0][18] = 239744224, f[0][19] = 299957786,
      f[0][20] = 246712224, f[0][21] = 130833350, f[0][22] = 42993694,
      f[0][23] = 8139682, f[0][24] = 790732, f[0][25] = 33846, f[0][26] = 454,
      f[0][27] = 0, f[0][28] = 0, f[0][29] = 0, f[0][30] = 0, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 40 && p[0] == 5 && d29 == 0 && d31 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 889, f[0][11] = 97708, f[0][12] = 2291254, f[0][13] = 27214952,
      f[0][14] = 199942860, f[0][15] = 963984306, f[0][16] = 122377527,
      f[0][17] = 848352134, f[0][18] = 192173750, f[0][19] = 270147862,
      f[0][20] = 937772500, f[0][21] = 73388911, f[0][22] = 857232092,
      f[0][23] = 140373302, f[0][24] = 12095134, f[0][25] = 469126,
      f[0][26] = 5742, f[0][27] = 0, f[0][28] = 0, f[0][29] = 0, f[0][30] = 0,
      f[0][31] = 0, f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0,
      f[0][36] = 0, f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0,
      ED();
    }
    if (m == 40 && p[0] == 5 && d29 && d31 == 0 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 206, f[0][12] = 9613, f[0][13] = 171828,
      f[0][14] = 1699424, f[0][15] = 10684738, f[0][16] = 44402696,
      f[0][17] = 123070612, f[0][18] = 227588052, f[0][19] = 279828552,
      f[0][20] = 226672908, f[0][21] = 118300966, f[0][22] = 38100170,
      f[0][23] = 7053276, f[0][24] = 670736, f[0][25] = 28082, f[0][26] = 346,
      f[0][27] = 0, f[0][28] = 0, f[0][29] = 0, f[0][30] = 0, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 40 && p[0] == 5 && d29 && d31 == 0 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 2467, f[0][11] = 132092, f[0][12] = 2682842,
      f[0][13] = 29740368, f[0][14] = 208093574, f[0][15] = 968564918,
      f[0][16] = 52632667, f[0][17] = 551778338, f[0][18] = 581965199,
      f[0][19] = 513068367, f[0][20] = 336312466, f[0][21] = 763197528,
      f[0][22] = 756308872, f[0][23] = 121323688, f[0][24] = 10244908,
      f[0][25] = 388668, f[0][26] = 4378, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 40 && p[0] == 5 && d29 && d31 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 24,
      f[0][10] = 5285, f[0][11] = 208220, f[0][12] = 3497270,
      f[0][13] = 34439076, f[0][14] = 220552234, f[0][15] = 955076744,
      f[0][16] = 833157574, f[0][17] = 777712771, f[0][18] = 91123270,
      f[0][19] = 739426025, f[0][20] = 992505790, f[0][21] = 117708604,
      f[0][22] = 565324882, f[0][23] = 88472834, f[0][24] = 7269162,
      f[0][25] = 265590, f[0][26] = 2804, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 40 && p[0] == 5 && d29 && d31 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 219, f[0][9] = 56862,
      f[0][10] = 2615574, f[0][11] = 50778066, f[0][12] = 566198330,
      f[0][13] = 75876394, f[0][14] = 885450171, f[0][15] = 113789175,
      f[0][16] = 287902, f[0][17] = 122793862, f[0][18] = 26304015,
      f[0][19] = 411520378, f[0][20] = 909860841, f[0][21] = 118620403,
      f[0][22] = 893093928, f[0][23] = 498500671, f[0][24] = 110234134,
      f[0][25] = 3664094, f[0][26] = 35492, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 38 && p[0] != 5 && d29 == 0 && d31 == 0 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 0, f[0][16] = 0, f[0][17] = 0, f[0][18] = 632,
      f[0][19] = 12742, f[0][20] = 116591, f[0][21] = 536188,
      f[0][22] = 1375418, f[0][23] = 2083720, f[0][24] = 1897566,
      f[0][25] = 1033872, f[0][26] = 322052, f[0][27] = 53078, f[0][28] = 4410,
      f[0][29] = 160, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 38 && p[0] != 5 && d29 == 0 && d31 == 0 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 0, f[0][16] = 0, f[0][17] = 11926, f[0][18] = 266469,
      f[0][19] = 2633950, f[0][20] = 13405350, f[0][21] = 38911000,
      f[0][22] = 68324116, f[0][23] = 74382134, f[0][24] = 50441216,
      f[0][25] = 20935008, f[0][26] = 5101244, f[0][27] = 686336,
      f[0][28] = 47704, f[0][29] = 1420, f[0][30] = 0, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 38 && p[0] != 5 && d29 == 0 && d31 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 0, f[0][16] = 374, f[0][17] = 24962, f[0][18] = 402443,
      f[0][19] = 3143022, f[0][20] = 13680608, f[0][21] = 35725828,
      f[0][22] = 58274066, f[0][23] = 60142448, f[0][24] = 39156818,
      f[0][25] = 15734576, f[0][26] = 3719546, f[0][27] = 489498,
      f[0][28] = 34098, f[0][29] = 1012, f[0][30] = 0, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 38 && p[0] != 5 && d29 == 0 && d31 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 6220, f[0][16] = 449307, f[0][17] = 8022530,
      f[0][18] = 68937046, f[0][19] = 334029656, f[0][20] = 985814392,
      f[0][21] = 849704617, f[0][22] = 248404384, f[0][23] = 777250869,
      f[0][24] = 905057218, f[0][25] = 289541790, f[0][26] = 55831630,
      f[0][27] = 6162440, f[0][28] = 362948, f[0][29] = 8988, f[0][30] = 0,
      f[0][31] = 0, f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0,
      f[0][36] = 0, f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0,
      ED();
    }
    if (m == 38 && p[0] != 5 && d29 && d31 == 0 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 0, f[0][16] = 596, f[0][17] = 28744, f[0][18] = 439071,
      f[0][19] = 3286308, f[0][20] = 13764068, f[0][21] = 34742372,
      f[0][22] = 54991594, f[0][23] = 55337858, f[0][24] = 35312068,
      f[0][25] = 13996256, f[0][26] = 3295376, f[0][27] = 431722,
      f[0][28] = 29542, f[0][29] = 866, f[0][30] = 0, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 38 && p[0] != 5 && d29 && d31 == 0 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 9978, f[0][16] = 523615, f[0][17] = 8790298,
      f[0][18] = 72376094, f[0][19] = 338031786, f[0][20] = 966010794,
      f[0][21] = 761682967, f[0][22] = 89524548, f[0][23] = 618408635,
      f[0][24] = 811524444, f[0][25] = 257241666, f[0][26] = 49421246,
      f[0][27] = 5420474, f[0][28] = 314062, f[0][29] = 7682, f[0][30] = 0,
      f[0][31] = 0, f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0,
      f[0][36] = 0, f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0,
      ED();
    }
    if (m == 38 && p[0] != 5 && d29 && d31 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 150,
      f[0][15] = 25156, f[0][16] = 883229, f[0][17] = 11807200,
      f[0][18] = 82375364, f[0][19] = 340883880, f[0][20] = 890574630,
      f[0][21] = 518736133, f[0][22] = 712432103, f[0][23] = 275799095,
      f[0][24] = 620325242, f[0][25] = 191481826, f[0][26] = 35914730,
      f[0][27] = 3880142, f[0][28] = 225284, f[0][29] = 5486, f[0][30] = 0,
      f[0][31] = 0, f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0,
      f[0][36] = 0, f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0,
      ED();
    }
    if (m == 38 && p[0] != 5 && d29 && d31 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 2124,
      f[0][14] = 393921, f[0][15] = 15206110, f[0][16] = 225763576,
      f[0][17] = 752637669, f[0][18] = 126329370, f[0][19] = 31330530,
      f[0][20] = 981062416, f[0][21] = 771378127, f[0][22] = 873254328,
      f[0][23] = 766294388, f[0][24] = 950842026, f[0][25] = 295246481,
      f[0][26] = 518081950, f[0][27] = 47698460, f[0][28] = 2365962,
      f[0][29] = 48702, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 38 && p[0] == 5 && d29 == 0 && d31 == 0 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 106, f[0][13] = 4914,
      f[0][14] = 64285, f[0][15] = 463122, f[0][16] = 1984508,
      f[0][17] = 5305040, f[0][18] = 9057770, f[0][19] = 9926226,
      f[0][20] = 6810888, f[0][21] = 2820014, f[0][22] = 659988,
      f[0][23] = 80772, f[0][24] = 4442, f[0][25] = 70, f[0][26] = 0,
      f[0][27] = 0, f[0][28] = 0, f[0][29] = 0, f[0][30] = 0, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 38 && p[0] == 5 && d29 == 0 && d31 == 0 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 1286, f[0][12] = 68311, f[0][13] = 1039192,
      f[0][14] = 8537126, f[0][15] = 42254898, f[0][16] = 132255730,
      f[0][17] = 269038396, f[0][18] = 359785418, f[0][19] = 314134152,
      f[0][20] = 175156004, f[0][21] = 60134354, f[0][22] = 11990456,
      f[0][23] = 1280636, f[0][24] = 62516, f[0][25] = 890, f[0][26] = 0,
      f[0][27] = 0, f[0][28] = 0, f[0][29] = 0, f[0][30] = 0, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 38 && p[0] == 5 && d29 == 0 && d31 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 18, f[0][11] = 2974, f[0][12] = 97555, f[0][13] = 1261996,
      f[0][14] = 9225498, f[0][15] = 41770644, f[0][16] = 121980926,
      f[0][17] = 234645344, f[0][18] = 299700704, f[0][19] = 251993772,
      f[0][20] = 136376054, f[0][21] = 45683982, f[0][22] = 8923764,
      f[0][23] = 937414, f[0][24] = 45220, f[0][25] = 630, f[0][26] = 0,
      f[0][27] = 0, f[0][28] = 0, f[0][29] = 0, f[0][30] = 0, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 38 && p[0] == 5 && d29 == 0 && d31 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 186,
      f[0][10] = 33951, f[0][11] = 1276868, f[0][12] = 19192748,
      f[0][13] = 161463298, f[0][14] = 845248530, f[0][15] = 881408830,
      f[0][16] = 554383782, f[0][17] = 70981114, f[0][18] = 457263166,
      f[0][19] = 256397429, f[0][20] = 288580331, f[0][21] = 937461024,
      f[0][22] = 158860348, f[0][23] = 14725970, f[0][24] = 634464,
      f[0][25] = 8010, f[0][26] = 0, f[0][27] = 0, f[0][28] = 0, f[0][29] = 0,
      f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0, f[0][34] = 0,
      f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0, f[0][39] = 0,
      f[0][40] = 0, ED();
    }
    if (m == 38 && p[0] == 5 && d29 && d31 == 0 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 52, f[0][11] = 4708, f[0][12] = 119303, f[0][13] = 1389580,
      f[0][14] = 9570672, f[0][15] = 41619382, f[0][16] = 118180412,
      f[0][17] = 222819286, f[0][18] = 279991130, f[0][19] = 231753962,
      f[0][20] = 123397840, f[0][21] = 40718378, f[0][22] = 7861866,
      f[0][23] = 816672, f[0][24] = 38470, f[0][25] = 492, f[0][26] = 0,
      f[0][27] = 0, f[0][28] = 0, f[0][29] = 0, f[0][30] = 0, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 38 && p[0] == 5 && d29 && d31 == 0 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 524,
      f[0][10] = 54159, f[0][11] = 1586320, f[0][12] = 21406272,
      f[0][13] = 169354310, f[0][14] = 850696098, f[0][15] = 816492228,
      f[0][16] = 272551662, f[0][17] = 480098327, f[0][18] = 700394461,
      f[0][19] = 633961442, f[0][20] = 963105142, f[0][21] = 833637082,
      f[0][22] = 139750462, f[0][23] = 12807778, f[0][24] = 538824,
      f[0][25] = 6256, f[0][26] = 0, f[0][27] = 0, f[0][28] = 0, f[0][29] = 0,
      f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0, f[0][34] = 0,
      f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0, f[0][39] = 0,
      f[0][40] = 0, ED();
    }
    if (m == 38 && p[0] == 5 && d29 && d31 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 4, f[0][9] = 1118,
      f[0][10] = 85079, f[0][11] = 2065942, f[0][12] = 24949490,
      f[0][13] = 180475314, f[0][14] = 841762052, f[0][15] = 620343246,
      f[0][16] = 542199849, f[0][17] = 19645838, f[0][18] = 911829217,
      f[0][19] = 250807079, f[0][20] = 288440968, f[0][21] = 630589706,
      f[0][22] = 103797544, f[0][23] = 9362340, f[0][24] = 388936,
      f[0][25] = 4430, f[0][26] = 0, f[0][27] = 0, f[0][28] = 0, f[0][29] = 0,
      f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0, f[0][34] = 0,
      f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0, f[0][39] = 0,
      f[0][40] = 0, ED();
    }
    if (m == 38 && p[0] == 5 && d29 && d31 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 32, f[0][8] = 10301, f[0][9] = 898510,
      f[0][10] = 25491234, f[0][11] = 358625746, f[0][12] = 4342073,
      f[0][13] = 239758258, f[0][14] = 912469008, f[0][15] = 515062868,
      f[0][16] = 502656880, f[0][17] = 204906758, f[0][18] = 688082055,
      f[0][19] = 391278398, f[0][20] = 440494482, f[0][21] = 539157370,
      f[0][22] = 815244563, f[0][23] = 145710818, f[0][24] = 5434834,
      f[0][25] = 56330, f[0][26] = 0, f[0][27] = 0, f[0][28] = 0, f[0][29] = 0,
      f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0, f[0][34] = 0,
      f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0, f[0][39] = 0,
      f[0][40] = 0, ED();
    }
    if (m == 39 && p[0] != 5 && d29 == 0 && d31 == 0 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 0, f[0][16] = 0, f[0][17] = 0, f[0][18] = 18, f[0][19] = 2460,
      f[0][20] = 36062, f[0][21] = 234372, f[0][22] = 822244,
      f[0][23] = 1701040, f[0][24] = 2127598, f[0][25] = 1603412,
      f[0][26] = 710457, f[0][27] = 175008, f[0][28] = 22302, f[0][29] = 1410,
      f[0][30] = 46, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0, f[0][34] = 0,
      f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0, f[0][39] = 0,
      f[0][40] = 0, ED();
    }
    if (m == 39 && p[0] != 5 && d29 == 0 && d31 == 0 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 0, f[0][16] = 0, f[0][17] = 504, f[0][18] = 53410,
      f[0][19] = 826640, f[0][20] = 5760118, f[0][21] = 22153524,
      f[0][22] = 51378468, f[0][23] = 74225608, f[0][24] = 67231716,
      f[0][25] = 37824792, f[0][26] = 12876925, f[0][27] = 2531444,
      f[0][28] = 269500, f[0][29] = 14814, f[0][30] = 410, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 39 && p[0] != 5 && d29 == 0 && d31 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 0, f[0][16] = 0, f[0][17] = 2854, f[0][18] = 97468,
      f[0][19] = 1096814, f[0][20] = 6338700, f[0][21] = 21531594,
      f[0][22] = 45728212, f[0][23] = 61912038, f[0][24] = 53407022,
      f[0][25] = 28899930, f[0][26] = 9503753, f[0][27] = 1811820,
      f[0][28] = 188514, f[0][29] = 10308, f[0][30] = 272, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 39 && p[0] != 5 && d29 == 0 && d31 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 78, f[0][16] = 56750, f[0][17] = 1985002, f[0][18] = 24097156,
      f[0][19] = 151608742, f[0][20] = 568035584, f[0][21] = 351586725,
      f[0][22] = 95994490, f[0][23] = 132295530, f[0][24] = 414815243,
      f[0][25] = 602010266, f[0][26] = 159550535, f[0][27] = 25198412,
      f[0][28] = 2240204, f[0][29] = 106878, f[0][30] = 2426, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 39 && p[0] != 5 && d29 && d31 == 0 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 0, f[0][16] = 10, f[0][17] = 3954, f[0][18] = 112306,
      f[0][19] = 1176176, f[0][20] = 6504786, f[0][21] = 21344208,
      f[0][22] = 43916606, f[0][23] = 57828092, f[0][24] = 48710380,
      f[0][25] = 25892152, f[0][26] = 8416957, f[0][27] = 1580788,
      f[0][28] = 161178, f[0][29] = 8628, f[0][30] = 220, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 39 && p[0] != 5 && d29 && d31 == 0 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 270, f[0][16] = 77148, f[0][17] = 2300150, f[0][18] = 25962440,
      f[0][19] = 156242510, f[0][20] = 566129476, f[0][21] = 307800939,
      f[0][22] = 975550417, f[0][23] = 964264129, f[0][24] = 279314701,
      f[0][25] = 537017902, f[0][26] = 140724209, f[0][27] = 21902396,
      f[0][28] = 1910466, f[0][29] = 89176, f[0][30] = 1960, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 39 && p[0] != 5 && d29 && d31 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 0,
      f[0][15] = 1946, f[0][16] = 166216, f[0][17] = 3427922,
      f[0][18] = 31775218, f[0][19] = 166904360, f[0][20] = 546856818,
      f[0][21] = 170126025, f[0][22] = 666050799, f[0][23] = 582242375,
      f[0][24] = 993532836, f[0][25] = 404272568, f[0][26] = 102949267,
      f[0][27] = 15636936, f[0][28] = 1342778, f[0][29] = 62276,
      f[0][30] = 1310, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0, f[0][34] = 0,
      f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0, f[0][39] = 0,
      f[0][40] = 0, ED();
    }
    if (m == 39 && p[0] != 5 && d29 && d31 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 0, f[0][13] = 0, f[0][14] = 34146,
      f[0][15] = 2985186, f[0][16] = 66410182, f[0][17] = 672854000,
      f[0][18] = 886850531, f[0][19] = 130217100, f[0][20] = 940211797,
      f[0][21] = 113539863, f[0][22] = 968391028, f[0][23] = 839143637,
      f[0][24] = 168380015, f[0][25] = 708390387, f[0][26] = 633464190,
      f[0][27] = 210720280, f[0][28] = 15694390, f[0][29] = 637730,
      f[0][30] = 11678, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0, f[0][34] = 0,
      f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0, f[0][39] = 0,
      f[0][40] = 0, ED();
    }
    if (m == 39 && p[0] == 5 && d29 == 0 && d31 == 0 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 0, f[0][12] = 6, f[0][13] = 1184,
      f[0][14] = 20604, f[0][15] = 188546, f[0][16] = 1028876,
      f[0][17] = 3461914, f[0][18] = 7374204, f[0][19] = 10051878,
      f[0][20] = 8689857, f[0][21] = 4635460, f[0][22] = 1455806,
      f[0][23] = 250488, f[0][24] = 22324, f[0][25] = 978, f[0][26] = 20,
      f[0][27] = 0, f[0][28] = 0, f[0][29] = 0, f[0][30] = 0, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 39 && p[0] == 5 && d29 == 0 && d31 == 0 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 72, f[0][12] = 16628, f[0][13] = 335142,
      f[0][14] = 3433786, f[0][15] = 21080716, f[0][16] = 81274342,
      f[0][17] = 202251742, f[0][18] = 329803718, f[0][19] = 352880186,
      f[0][20] = 244715495, f[0][21] = 107070850, f[0][22] = 28286514,
      f[0][23] = 4237114, f[0][24] = 339172, f[0][25] = 13638, f[0][26] = 250,
      f[0][27] = 0, f[0][28] = 0, f[0][29] = 0, f[0][30] = 0, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 39 && p[0] == 5 && d29 == 0 && d31 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 0, f[0][11] = 508, f[0][12] = 27118, f[0][13] = 438042,
      f[0][14] = 3919840, f[0][15] = 21731838, f[0][16] = 77428240,
      f[0][17] = 181093112, f[0][18] = 280702904, f[0][19] = 287934294,
      f[0][20] = 192841235, f[0][21] = 82021900, f[0][22] = 21151478,
      f[0][23] = 3104252, f[0][24] = 242304, f[0][25] = 9270, f[0][26] = 160,
      f[0][27] = 0, f[0][28] = 0, f[0][29] = 0, f[0][30] = 0, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 39 && p[0] == 5 && d29 == 0 && d31 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 5842, f[0][11] = 357936, f[0][12] = 6686110,
      f[0][13] = 67731066, f[0][14] = 425467882, f[0][15] = 736627917,
      f[0][16] = 720067956, f[0][17] = 656347400, f[0][18] = 755744020,
      f[0][19] = 10241333, f[0][20] = 12201250, f[0][21] = 800678095,
      f[0][22] = 400134126, f[0][23] = 51843076, f[0][24] = 3655504,
      f[0][25] = 128536, f[0][26] = 2000, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 39 && p[0] == 5 && d29 && d31 == 0 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 0,
      f[0][10] = 4, f[0][11] = 922, f[0][12] = 34618, f[0][13] = 499748,
      f[0][14] = 4181614, f[0][15] = 22092024, f[0][16] = 76059968,
      f[0][17] = 173468274, f[0][18] = 264025680, f[0][19] = 266779826,
      f[0][20] = 176054273, f[0][21] = 73625248, f[0][22] = 18591106,
      f[0][23] = 2659160, f[0][24] = 202098, f[0][25] = 7522, f[0][26] = 120,
      f[0][27] = 0, f[0][28] = 0, f[0][29] = 0, f[0][30] = 0, f[0][31] = 0,
      f[0][32] = 0, f[0][33] = 0, f[0][34] = 0, f[0][35] = 0, f[0][36] = 0,
      f[0][37] = 0, f[0][38] = 0, f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 39 && p[0] == 5 && d29 && d31 == 0 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 40,
      f[0][10] = 10842, f[0][11] = 464332, f[0][12] = 7704440,
      f[0][13] = 72909678, f[0][14] = 436610436, f[0][15] = 721396137,
      f[0][16] = 559871700, f[0][17] = 203504638, f[0][18] = 40086352,
      f[0][19] = 297143590, f[0][20] = 550836405, f[0][21] = 608272369,
      f[0][22] = 350203402, f[0][23] = 44277826, f[0][24] = 3043494,
      f[0][25] = 104152, f[0][26] = 1500, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 39 && p[0] == 5 && d29 && d31 && d37 == 0) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 142,
      f[0][10] = 20518, f[0][11] = 655840, f[0][12] = 9457836,
      f[0][13] = 80947454, f[0][14] = 446702388, f[0][15] = 646383185,
      f[0][16] = 124050924, f[0][17] = 78751205, f[0][18] = 324290074,
      f[0][19] = 650645548, f[0][20] = 545892968, f[0][21] = 223531373,
      f[0][22] = 260848972, f[0][23] = 32333078, f[0][24] = 2165142,
      f[0][25] = 70538, f[0][26] = 960, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (m == 39 && p[0] == 5 && d29 && d31 && d37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 1316, f[0][9] = 219154,
      f[0][10] = 8143192, f[0][11] = 135936196, f[0][12] = 328988581,
      f[0][13] = 368617060, f[0][14] = 387711461, f[0][15] = 686281396,
      f[0][16] = 837445742, f[0][17] = 410429306, f[0][18] = 482773435,
      f[0][19] = 503549954, f[0][20] = 502854595, f[0][21] = 756545545,
      f[0][22] = 814011308, f[0][23] = 532773622, f[0][24] = 32414136,
      f[0][25] = 972526, f[0][26] = 12000, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
  }
  if (m == 40 && tot == 6 && p[0] == 5 && __builtin_popcountll(s0) == 1 &&
      d23 && d29 && d31 && d37) {
    int pz = 0;
    for (int i = 1; i <= m; i++)
      if (sss[i] == '1') pz = i;
    if (pz == 1) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 1097,
      f[0][10] = 163389, f[0][11] = 5691007, f[0][12] = 90849137,
      f[0][13] = 853639395, f[0][14] = 146380054, f[0][15] = 648641351,
      f[0][16] = 221133565, f[0][17] = 58291398, f[0][18] = 345926842,
      f[0][19] = 802396262, f[0][20] = 894425838, f[0][21] = 487419592,
      f[0][22] = 125344727, f[0][23] = 46262107, f[0][24] = 80535058,
      f[0][25] = 2715060, f[0][26] = 23492, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 2) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 2571,
      f[0][10] = 239685, f[0][11] = 7107528, f[0][12] = 106135343,
      f[0][13] = 951171093, f[0][14] = 529624918, f[0][15] = 621246994,
      f[0][16] = 821143778, f[0][17] = 561040857, f[0][18] = 535704416,
      f[0][19] = 380695122, f[0][20] = 54662044, f[0][21] = 388605203,
      f[0][22] = 780267661, f[0][23] = 992445482, f[0][24] = 77064909,
      f[0][25] = 2654915, f[0][26] = 26866, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 3) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 2812,
      f[0][10] = 275611, f[0][11] = 8026577, f[0][12] = 116379002,
      f[0][13] = 16132080, f[0][14] = 790668022, f[0][15] = 304954961,
      f[0][16] = 961524908, f[0][17] = 576462460, f[0][18] = 498420447,
      f[0][19] = 233333867, f[0][20] = 819223814, f[0][21] = 777497287,
      f[0][22] = 639096694, f[0][23] = 985322042, f[0][24] = 79516654,
      f[0][25] = 2969535, f[0][26] = 32612, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 4) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 4452,
      f[0][10] = 356390, f[0][11] = 9698263, f[0][12] = 133552108,
      f[0][13] = 118089554, f[0][14] = 150647262, f[0][15] = 28922441,
      f[0][16] = 626813099, f[0][17] = 422016604, f[0][18] = 605168526,
      f[0][19] = 511015667, f[0][20] = 639826299, f[0][21] = 825546725,
      f[0][22] = 670108397, f[0][23] = 987033688, f[0][24] = 78215857,
      f[0][25] = 2794300, f[0][26] = 29746, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 5) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 3388,
      f[0][10] = 338612, f[0][11] = 9251358, f[0][12] = 130411027,
      f[0][13] = 114547459, f[0][14] = 191802283, f[0][15] = 199738469,
      f[0][16] = 828255942, f[0][17] = 291398160, f[0][18] = 150528284,
      f[0][19] = 282500345, f[0][20] = 793415902, f[0][21] = 13446372,
      f[0][22] = 731988462, f[0][23] = 992118543, f[0][24] = 77402704,
      f[0][25] = 2668569, f[0][26] = 23492, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 6) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 8, f[0][9] = 8843,
      f[0][10] = 558670, f[0][11] = 12774796, f[0][12] = 162021393,
      f[0][13] = 306041893, f[0][14] = 22259356, f[0][15] = 692408475,
      f[0][16] = 628694970, f[0][17] = 375090860, f[0][18] = 244189139,
      f[0][19] = 162246923, f[0][20] = 227369691, f[0][21] = 584781124,
      f[0][22] = 562857871, f[0][23] = 770787251, f[0][24] = 55927325,
      f[0][25] = 1803037, f[0][26] = 17746, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 7) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 33, f[0][9] = 13406,
      f[0][10] = 720364, f[0][11] = 15358163, f[0][12] = 185783298,
      f[0][13] = 435918450, f[0][14] = 456612243, f[0][15] = 603792420,
      f[0][16] = 804705860, f[0][17] = 124626437, f[0][18] = 951412889,
      f[0][19] = 3346919, f[0][20] = 61344224, f[0][21] = 972953219,
      f[0][22] = 389022726, f[0][23] = 747326953, f[0][24] = 55057286,
      f[0][25] = 1825968, f[0][26] = 18520, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 8) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 24, f[0][9] = 10400,
      f[0][10] = 608029, f[0][11] = 13590750, f[0][12] = 168605881,
      f[0][13] = 327201660, f[0][14] = 15986138, f[0][15] = 473178983,
      f[0][16] = 48024878, f[0][17] = 796217508, f[0][18] = 270994064,
      f[0][19] = 697444872, f[0][20] = 704051764, f[0][21] = 803118971,
      f[0][22] = 636614851, f[0][23] = 792278657, f[0][24] = 59829141,
      f[0][25] = 2064541, f[0][26] = 18266, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 9) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 14106,
      f[0][10] = 705306, f[0][11] = 14694655, f[0][12] = 176335883,
      f[0][13] = 362414264, f[0][14] = 110716784, f[0][15] = 596829596,
      f[0][16] = 48616754, f[0][17] = 577136594, f[0][18] = 2976065,
      f[0][19] = 628385558, f[0][20] = 819812368, f[0][21] = 922119157,
      f[0][22] = 685059456, f[0][23] = 801540040, f[0][24] = 60415718,
      f[0][25] = 2046968, f[0][26] = 20106, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 10) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 49, f[0][9] = 13915,
      f[0][10] = 746352, f[0][11] = 15775184, f[0][12] = 187581232,
      f[0][13] = 429267863, f[0][14] = 362623131, f[0][15] = 189631369,
      f[0][16] = 831014367, f[0][17] = 912539104, f[0][18] = 498663776,
      f[0][19] = 786243749, f[0][20] = 295421876, f[0][21] = 767895398,
      f[0][22] = 667454175, f[0][23] = 802157890, f[0][24] = 60725634,
      f[0][25] = 2064469, f[0][26] = 19852, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 11) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 49, f[0][9] = 17339,
      f[0][10] = 846757, f[0][11] = 16897761, f[0][12] = 194514592,
      f[0][13] = 457699434, f[0][14] = 438006384, f[0][15] = 300409828,
      f[0][16] = 867413977, f[0][17] = 763461014, f[0][18] = 247576588,
      f[0][19] = 652643518, f[0][20] = 354173760, f[0][21] = 890374547,
      f[0][22] = 738603722, f[0][23] = 821635914, f[0][24] = 63296553,
      f[0][25] = 2246262, f[0][26] = 21386, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 12) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 72, f[0][9] = 20417,
      f[0][10] = 886399, f[0][11] = 17285919, f[0][12] = 195967524,
      f[0][13] = 446682083, f[0][14] = 301827458, f[0][15] = 702746915,
      f[0][16] = 506551094, f[0][17] = 171784520, f[0][18] = 735409722,
      f[0][19] = 706281007, f[0][20] = 971340515, f[0][21] = 963220673,
      f[0][22] = 123371615, f[0][23] = 894451131, f[0][24] = 69591341,
      f[0][25] = 2397234, f[0][26] = 23746, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 13) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 72, f[0][9] = 19152,
      f[0][10] = 936494, f[0][11] = 18490027, f[0][12] = 209640166,
      f[0][13] = 552241418, f[0][14] = 850207562, f[0][15] = 516692859,
      f[0][16] = 144970560, f[0][17] = 109588202, f[0][18] = 703348447,
      f[0][19] = 685386869, f[0][20] = 738080291, f[0][21] = 297849368,
      f[0][22] = 203516769, f[0][23] = 722695759, f[0][24] = 54227272,
      f[0][25] = 1924345, f[0][26] = 23746, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 14) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 56, f[0][9] = 14848,
      f[0][10] = 764614, f[0][11] = 16238832, f[0][12] = 193477024,
      f[0][13] = 470448516, f[0][14] = 532779499, f[0][15] = 622973458,
      f[0][16] = 497180730, f[0][17] = 430872293, f[0][18] = 417981907,
      f[0][19] = 160306889, f[0][20] = 653948538, f[0][21] = 427774414,
      f[0][22] = 552104593, f[0][23] = 774500356, f[0][24] = 56633889,
      f[0][25] = 1818816, f[0][26] = 20106, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 15) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 97, f[0][9] = 15477,
      f[0][10] = 756922, f[0][11] = 15716260, f[0][12] = 186881664,
      f[0][13] = 423430790, f[0][14] = 301088861, f[0][15] = 824955922,
      f[0][16] = 706755658, f[0][17] = 130577993, f[0][18] = 400046395,
      f[0][19] = 518674551, f[0][20] = 86278182, f[0][21] = 100404002,
      f[0][22] = 155961548, f[0][23] = 889303317, f[0][24] = 66844556,
      f[0][25] = 2129684, f[0][26] = 17492, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 16) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 66, f[0][9] = 18542,
      f[0][10] = 826723, f[0][11] = 16362617, f[0][12] = 189762615,
      f[0][13] = 429001951, f[0][14] = 294438841, f[0][15] = 773232809,
      f[0][16] = 642652286, f[0][17] = 178476832, f[0][18] = 543604422,
      f[0][19] = 565284402, f[0][20] = 6372155, f[0][21] = 39563600,
      f[0][22] = 156276899, f[0][23] = 901044159, f[0][24] = 70419432,
      f[0][25] = 2477528, f[0][26] = 23492, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 17) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 121, f[0][9] = 18372,
      f[0][10] = 808209, f[0][11] = 16232449, f[0][12] = 187587160,
      f[0][13] = 404774993, f[0][14] = 176963454, f[0][15] = 513501178,
      f[0][16] = 470011179, f[0][17] = 482816476, f[0][18] = 148890739,
      f[0][19] = 816198583, f[0][20] = 795174359, f[0][21] = 784198457,
      f[0][22] = 55603043, f[0][23] = 884703552, f[0][24] = 69793365,
      f[0][25] = 2533943, f[0][26] = 29746, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 18) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 82, f[0][9] = 17812,
      f[0][10] = 810451, f[0][11] = 15667922, f[0][12] = 179501345,
      f[0][13] = 357294831, f[0][14] = 27102088, f[0][15] = 236225029,
      f[0][16] = 178570546, f[0][17] = 379408365, f[0][18] = 286488974,
      f[0][19] = 45080856, f[0][20] = 3111281, f[0][21] = 948693158,
      f[0][22] = 153452555, f[0][23] = 919322601, f[0][24] = 76056364,
      f[0][25] = 2999612, f[0][26] = 35492, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 19) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 89, f[0][9] = 21074,
      f[0][10] = 904485, f[0][11] = 17535186, f[0][12] = 200875363,
      f[0][13] = 496412134, f[0][14] = 580091694, f[0][15] = 617437289,
      f[0][16] = 263063071, f[0][17] = 925481855, f[0][18] = 987354456,
      f[0][19] = 200571661, f[0][20] = 68394951, f[0][21] = 821428222,
      f[0][22] = 741106073, f[0][23] = 823883584, f[0][24] = 63069865,
      f[0][25] = 2184587, f[0][26] = 23746, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 20) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 58, f[0][9] = 17856,
      f[0][10] = 824408, f[0][11] = 16884109, f[0][12] = 201328223,
      f[0][13] = 540786756, f[0][14] = 918325172, f[0][15] = 885898533,
      f[0][16] = 905206071, f[0][17] = 776460351, f[0][18] = 662050100,
      f[0][19] = 71406006, f[0][20] = 112180558, f[0][21] = 928624823,
      f[0][22] = 56221364, f[0][23] = 683944764, f[0][24] = 48186685,
      f[0][25] = 1481802, f[0][26] = 11746, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 21) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 58, f[0][9] = 17856,
      f[0][10] = 824408, f[0][11] = 16884109, f[0][12] = 201328223,
      f[0][13] = 540786756, f[0][14] = 918325172, f[0][15] = 885898533,
      f[0][16] = 905206071, f[0][17] = 776460351, f[0][18] = 662050100,
      f[0][19] = 71406006, f[0][20] = 112180558, f[0][21] = 928624823,
      f[0][22] = 56221364, f[0][23] = 683944764, f[0][24] = 48186685,
      f[0][25] = 1481802, f[0][26] = 11746, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 22) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 89, f[0][9] = 21074,
      f[0][10] = 904485, f[0][11] = 17535186, f[0][12] = 200875363,
      f[0][13] = 496412134, f[0][14] = 580091694, f[0][15] = 617437289,
      f[0][16] = 263063071, f[0][17] = 925481855, f[0][18] = 987354456,
      f[0][19] = 200571661, f[0][20] = 68394951, f[0][21] = 821428222,
      f[0][22] = 741106073, f[0][23] = 823883584, f[0][24] = 63069865,
      f[0][25] = 2184587, f[0][26] = 23746, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 23) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 82, f[0][9] = 17812,
      f[0][10] = 810451, f[0][11] = 15667922, f[0][12] = 179501345,
      f[0][13] = 357294831, f[0][14] = 27102088, f[0][15] = 236225029,
      f[0][16] = 178570546, f[0][17] = 379408365, f[0][18] = 286488974,
      f[0][19] = 45080856, f[0][20] = 3111281, f[0][21] = 948693158,
      f[0][22] = 153452555, f[0][23] = 919322601, f[0][24] = 76056364,
      f[0][25] = 2999612, f[0][26] = 35492, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 24) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 121, f[0][9] = 18372,
      f[0][10] = 808209, f[0][11] = 16232449, f[0][12] = 187587160,
      f[0][13] = 404774993, f[0][14] = 176963454, f[0][15] = 513501178,
      f[0][16] = 470011179, f[0][17] = 482816476, f[0][18] = 148890739,
      f[0][19] = 816198583, f[0][20] = 795174359, f[0][21] = 784198457,
      f[0][22] = 55603043, f[0][23] = 884703552, f[0][24] = 69793365,
      f[0][25] = 2533943, f[0][26] = 29746, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 25) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 66, f[0][9] = 18542,
      f[0][10] = 826723, f[0][11] = 16362617, f[0][12] = 189762615,
      f[0][13] = 429001951, f[0][14] = 294438841, f[0][15] = 773232809,
      f[0][16] = 642652286, f[0][17] = 178476832, f[0][18] = 543604422,
      f[0][19] = 565284402, f[0][20] = 6372155, f[0][21] = 39563600,
      f[0][22] = 156276899, f[0][23] = 901044159, f[0][24] = 70419432,
      f[0][25] = 2477528, f[0][26] = 23492, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 26) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 97, f[0][9] = 15477,
      f[0][10] = 756922, f[0][11] = 15716260, f[0][12] = 186881664,
      f[0][13] = 423430790, f[0][14] = 301088861, f[0][15] = 824955922,
      f[0][16] = 706755658, f[0][17] = 130577993, f[0][18] = 400046395,
      f[0][19] = 518674551, f[0][20] = 86278182, f[0][21] = 100404002,
      f[0][22] = 155961548, f[0][23] = 889303317, f[0][24] = 66844556,
      f[0][25] = 2129684, f[0][26] = 17492, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 27) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 56, f[0][9] = 14848,
      f[0][10] = 764614, f[0][11] = 16238832, f[0][12] = 193477024,
      f[0][13] = 470448516, f[0][14] = 532779499, f[0][15] = 622973458,
      f[0][16] = 497180730, f[0][17] = 430872293, f[0][18] = 417981907,
      f[0][19] = 160306889, f[0][20] = 653948538, f[0][21] = 427774414,
      f[0][22] = 552104593, f[0][23] = 774500356, f[0][24] = 56633889,
      f[0][25] = 1818816, f[0][26] = 20106, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 28) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 72, f[0][9] = 19152,
      f[0][10] = 936494, f[0][11] = 18490027, f[0][12] = 209640166,
      f[0][13] = 552241418, f[0][14] = 850207562, f[0][15] = 516692859,
      f[0][16] = 144970560, f[0][17] = 109588202, f[0][18] = 703348447,
      f[0][19] = 685386869, f[0][20] = 738080291, f[0][21] = 297849368,
      f[0][22] = 203516769, f[0][23] = 722695759, f[0][24] = 54227272,
      f[0][25] = 1924345, f[0][26] = 23746, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 29) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 72, f[0][9] = 20417,
      f[0][10] = 886399, f[0][11] = 17285919, f[0][12] = 195967524,
      f[0][13] = 446682083, f[0][14] = 301827458, f[0][15] = 702746915,
      f[0][16] = 506551094, f[0][17] = 171784520, f[0][18] = 735409722,
      f[0][19] = 706281007, f[0][20] = 971340515, f[0][21] = 963220673,
      f[0][22] = 123371615, f[0][23] = 894451131, f[0][24] = 69591341,
      f[0][25] = 2397234, f[0][26] = 23746, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 30) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 49, f[0][9] = 17339,
      f[0][10] = 846757, f[0][11] = 16897761, f[0][12] = 194514592,
      f[0][13] = 457699434, f[0][14] = 438006384, f[0][15] = 300409828,
      f[0][16] = 867413977, f[0][17] = 763461014, f[0][18] = 247576588,
      f[0][19] = 652643518, f[0][20] = 354173760, f[0][21] = 890374547,
      f[0][22] = 738603722, f[0][23] = 821635914, f[0][24] = 63296553,
      f[0][25] = 2246262, f[0][26] = 21386, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 31) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 49, f[0][9] = 13915,
      f[0][10] = 746352, f[0][11] = 15775184, f[0][12] = 187581232,
      f[0][13] = 429267863, f[0][14] = 362623131, f[0][15] = 189631369,
      f[0][16] = 831014367, f[0][17] = 912539104, f[0][18] = 498663776,
      f[0][19] = 786243749, f[0][20] = 295421876, f[0][21] = 767895398,
      f[0][22] = 667454175, f[0][23] = 802157890, f[0][24] = 60725634,
      f[0][25] = 2064469, f[0][26] = 19852, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 32) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 14106,
      f[0][10] = 705306, f[0][11] = 14694655, f[0][12] = 176335883,
      f[0][13] = 362414264, f[0][14] = 110716784, f[0][15] = 596829596,
      f[0][16] = 48616754, f[0][17] = 577136594, f[0][18] = 2976065,
      f[0][19] = 628385558, f[0][20] = 819812368, f[0][21] = 922119157,
      f[0][22] = 685059456, f[0][23] = 801540040, f[0][24] = 60415718,
      f[0][25] = 2046968, f[0][26] = 20106, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 33) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 24, f[0][9] = 10400,
      f[0][10] = 608029, f[0][11] = 13590750, f[0][12] = 168605881,
      f[0][13] = 327201660, f[0][14] = 15986138, f[0][15] = 473178983,
      f[0][16] = 48024878, f[0][17] = 796217508, f[0][18] = 270994064,
      f[0][19] = 697444872, f[0][20] = 704051764, f[0][21] = 803118971,
      f[0][22] = 636614851, f[0][23] = 792278657, f[0][24] = 59829141,
      f[0][25] = 2064541, f[0][26] = 18266, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 34) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 33, f[0][9] = 13406,
      f[0][10] = 720364, f[0][11] = 15358163, f[0][12] = 185783298,
      f[0][13] = 435918450, f[0][14] = 456612243, f[0][15] = 603792420,
      f[0][16] = 804705860, f[0][17] = 124626437, f[0][18] = 951412889,
      f[0][19] = 3346919, f[0][20] = 61344224, f[0][21] = 972953219,
      f[0][22] = 389022726, f[0][23] = 747326953, f[0][24] = 55057286,
      f[0][25] = 1825968, f[0][26] = 18520, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 35) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 8, f[0][9] = 8843,
      f[0][10] = 558670, f[0][11] = 12774796, f[0][12] = 162021393,
      f[0][13] = 306041893, f[0][14] = 22259356, f[0][15] = 692408475,
      f[0][16] = 628694970, f[0][17] = 375090860, f[0][18] = 244189139,
      f[0][19] = 162246923, f[0][20] = 227369691, f[0][21] = 584781124,
      f[0][22] = 562857871, f[0][23] = 770787251, f[0][24] = 55927325,
      f[0][25] = 1803037, f[0][26] = 17746, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 36) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 3388,
      f[0][10] = 338612, f[0][11] = 9251358, f[0][12] = 130411027,
      f[0][13] = 114547459, f[0][14] = 191802283, f[0][15] = 199738469,
      f[0][16] = 828255942, f[0][17] = 291398160, f[0][18] = 150528284,
      f[0][19] = 282500345, f[0][20] = 793415902, f[0][21] = 13446372,
      f[0][22] = 731988462, f[0][23] = 992118543, f[0][24] = 77402704,
      f[0][25] = 2668569, f[0][26] = 23492, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 37) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 4452,
      f[0][10] = 356390, f[0][11] = 9698263, f[0][12] = 133552108,
      f[0][13] = 118089554, f[0][14] = 150647262, f[0][15] = 28922441,
      f[0][16] = 626813099, f[0][17] = 422016604, f[0][18] = 605168526,
      f[0][19] = 511015667, f[0][20] = 639826299, f[0][21] = 825546725,
      f[0][22] = 670108397, f[0][23] = 987033688, f[0][24] = 78215857,
      f[0][25] = 2794300, f[0][26] = 29746, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 38) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 2812,
      f[0][10] = 275611, f[0][11] = 8026577, f[0][12] = 116379002,
      f[0][13] = 16132080, f[0][14] = 790668022, f[0][15] = 304954961,
      f[0][16] = 961524908, f[0][17] = 576462460, f[0][18] = 498420447,
      f[0][19] = 233333867, f[0][20] = 819223814, f[0][21] = 777497287,
      f[0][22] = 639096694, f[0][23] = 985322042, f[0][24] = 79516654,
      f[0][25] = 2969535, f[0][26] = 32612, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 39) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 2571,
      f[0][10] = 239685, f[0][11] = 7107528, f[0][12] = 106135343,
      f[0][13] = 951171093, f[0][14] = 529624918, f[0][15] = 621246994,
      f[0][16] = 821143778, f[0][17] = 561040857, f[0][18] = 535704416,
      f[0][19] = 380695122, f[0][20] = 54662044, f[0][21] = 388605203,
      f[0][22] = 780267661, f[0][23] = 992445482, f[0][24] = 77064909,
      f[0][25] = 2654915, f[0][26] = 26866, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
    if (pz == 40) {
      f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, f[0][3] = 0, f[0][4] = 0,
      f[0][5] = 0, f[0][6] = 0, f[0][7] = 0, f[0][8] = 0, f[0][9] = 1097,
      f[0][10] = 163389, f[0][11] = 5691007, f[0][12] = 90849137,
      f[0][13] = 853639395, f[0][14] = 146380054, f[0][15] = 648641351,
      f[0][16] = 221133565, f[0][17] = 58291398, f[0][18] = 345926842,
      f[0][19] = 802396262, f[0][20] = 894425838, f[0][21] = 487419592,
      f[0][22] = 125344727, f[0][23] = 46262107, f[0][24] = 80535058,
      f[0][25] = 2715060, f[0][26] = 23492, f[0][27] = 0, f[0][28] = 0,
      f[0][29] = 0, f[0][30] = 0, f[0][31] = 0, f[0][32] = 0, f[0][33] = 0,
      f[0][34] = 0, f[0][35] = 0, f[0][36] = 0, f[0][37] = 0, f[0][38] = 0,
      f[0][39] = 0, f[0][40] = 0, ED();
    }
  }
  for (int i = 0; i < tot; i++) {
    uz.clear();
    lst = bok, bok.clear();
    for (int st = 1; st <= p[i]; st++) {
      long long owo = 0;
      for (int j = st; j <= m; j += p[i]) owo |= (1ll << j);
      owo ^= all;
      if ((owo & s0) == s0) uz.push_back(owo);
    }
    for (auto o : lst)
      for (long long p : uz) bok[o.first & p] += o.second;
  }
  if (d23) D(23);
  if (d29) D(29);
  if (d31) D(31);
  if (d37) D(37);
  for (auto it : bok) {
    int num = (it.first >> 45) + __builtin_popcountll(it.first & W(1, m));
    f[0][num] = add(f[0][num], it.second % 1000000007);
  }
  ED();
  return 0;
}