#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

bool table[12][4] = {
  0,0,0,0,
    1,0,1,0,
    0,1,0,1,
    1,1,0,0,
    0,1,1,0,
    0,0,1,1,
    1,0,0,1,
    1,1,1,0,
    0,1,1,1,
    1,0,1,1,
    1,1,0,1,
    1,1,1,1
    };
bool connect[12][12][4];

void init() {
  REP(i,12) {
    REP(j,12) {
      REP(k,4) {
        connect[i][j][k] = table[i][k] && table[j][(k+2)%4];
      }
    }
  }
}

int enc[15][1<<15];

void init2(int R, int C, int N) {
  int num = 0;
  REP(i,C) {
    int perm[N];
    REP(j,N) {
      if (j<N-R*i) perm[j] = 0;
      else perm[j] = 1;
    }
    do {
      int S = 0;
      REP(j,N) if (perm[j]) S |= 1<<j;
      enc[i][S] = num++;
    } while(next_permutation(perm,perm+N));
  }
}

// S:始点との接続状態
// T:セル同士の接続状態
// 流れるなら流れた状態にする
void func(int &S, int &T) {
  bool f = 0;
  REP(i,3) if ((T>>i&1) && (S>>i&1)) f = 1;
  if (f) REP(i,3) if (T>>i&1) S |= 1<<i;
}

int encode(int S, int T) {
  if (S==0) return 0;
  if (S==1 && T==6) return 7;
  if (S==2 && T==5) return 8;
  if (S==4 && T==3) return 9;
  return S-1;
}

// pii decode(int x) {
//   if (x==7) return pii(1,6);
//   if (x==8) return pii(2,5);
//   if (x==9) return pii(4,3);
//   return pii(x+1,0);
// }

ll memo[40000][10][1<<3];
int R, C;
int N;

int pnum[12];
int pkind[15];
int pmp[12][15];

ll solve(int x, int U, int S, int T, int Q);

ll dfs(int x, int U, int S, int T, int Q, int NU, int num, int id) {
  if (id == 12) {
    if (num == R) {
      int k = 0;
      int perm[3] = {};
      REP(i,N) {
        if (NU>>i&1) {
          perm[k++] = pkind[i];
        }
      }
      // if (x == 2) {
      //   cout << "x = " << x << endl;
      //   REP(i,num) cout << perm[i] << " "; cout << endl;
      //   cout << bitset<9>(U) <<" " << bitset<3>(S) << " " << bitset<3>(T) << " " << bitset<3>(Q) << endl;
      // }
      ll res = 0;
      do {
        int nS = 0;
        int nT = 0;
        int nQ = 0;
        REP(i,R) {
          if ((Q>>i&1) && table[perm[i]][3]) {
            if (S>>i&1) nS|=1<<i;
            if (T>>i&1) nT |= 1<<i;
          }
          if (table[perm[i]][1]) nQ |= 1<<i;
        }
        //assert(__builtin_popcount(nT) == 0);
        if (__builtin_popcount(nT) == 1) nT = 0;
        if (connect[perm[0]][perm[1]][2]) nT |= 3;
        if (connect[perm[1]][perm[2]][2]) nT |= 6;
        
        if (x == 0) nS |= 1;    // 1列目の1行目は始点
        
        func(nS,nT);
        if (nS) {
          res += solve(x+1, U|NU, nS, nT, nQ);
        }
      } while(next_permutation(perm, perm+R));
      return res;
    } else return 0;
  }
  ll res = 0;
  
  int pct[12] = {};
  REP(i,N) {
    if (U>>i&1) {
      pct[pkind[i]]++;
    }
  }
  REP(i,R-num+1) {
    if (pct[id]+i <= pnum[id]) {
      int UU = NU;
      REP(j,i) UU |= 1<<pmp[id][pct[id]+j];
      res += dfs(x,U,S,T,Q,UU, num+i, id+1);
    } else break;
  }
  return res;
}

ll solve(int x, int U, int S, int T, int Q) {
  if (x == C) {
    // cout << "x = " << x << endl;
    // cout << bitset<9>(U) <<" " << bitset<3>(S) << " " << bitset<3>(T) << " " << bitset<3>(Q) << endl;

    return (S>>(R-1)&1);
  }
  //cout << x << " " << bitset<15>(U) << " "<< enc[x][U] << endl;
  assert(enc[x][U] >= 0);
  int p = encode(S,T);
  ll &r = memo[enc[x][U]][p][Q];
  if (r >= 0) return r;
  
  return r = dfs(x,U,S,T,Q,0,0,0);
}
  
int main() {
  init();
  cin >> R >> C;
  REP(i,12) cin >> pnum[i];
  if (R>C) {
    swap(R,C);
    swap(pnum[1],pnum[2]);
    swap(pnum[3],pnum[5]);
    swap(pnum[7],pnum[8]);
    swap(pnum[9],pnum[10]);
  }
  N = 0;
  REP(i,12) {
    REP(j,pnum[i]) {
      pkind[N] = i;
      pmp[i][j] = N;
      N++;
    }
  }
  // assert(R<=3);
  // assert(N<=15);
  memset(enc,-1,sizeof(enc));
  init2(R,C,N);
  memset(memo,-1,sizeof(memo));
  cout << solve(0,0,0,0,0) << endl;
}
### Prompt

In cpp, your task is to solve the following problem:

There are twelve types of tiles in Fig. 1. You were asked to fill a table with R × C cells with these tiles. R is the number of rows and C is the number of columns.

How many arrangements in the table meet the following constraints?

* Each cell has one tile.

* the center of the upper left cell (1,1) and the center of the lower right cell (C, R) are connected by some roads.




<image>

Fig. 1: the types of tiles



Input

The first line contains two integers R and C (2 ≤ R × C ≤ 15). You can safely assume at least one of R and C is greater than 1.
The second line contains twelve integers, t1, t2, ..., t12 (0 ≤ t1 + .... + t12 ≤ 15). ti represents the number of the i-th tiles you have.

Output

Output the number of arrangments in a line.

Examples

Input

3 3
4 2 2 0 0 0 0 0 0 0 0 1


Output

2


Input

3 3
0 1 1 0 0 0 0 0 0 0 0 7


Output

66


Input

3 3
0 0 0 0 0 0 0 0 0 0 0 10


Output

1


Input

2 4
0 0 1 1 1 2 0 1 0 0 1 1


Output

2012


Input

5 2
0 1 1 1 0 1 2 1 2 0 0 1


Output

8512

### Response

```cpp
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

bool table[12][4] = {
  0,0,0,0,
    1,0,1,0,
    0,1,0,1,
    1,1,0,0,
    0,1,1,0,
    0,0,1,1,
    1,0,0,1,
    1,1,1,0,
    0,1,1,1,
    1,0,1,1,
    1,1,0,1,
    1,1,1,1
    };
bool connect[12][12][4];

void init() {
  REP(i,12) {
    REP(j,12) {
      REP(k,4) {
        connect[i][j][k] = table[i][k] && table[j][(k+2)%4];
      }
    }
  }
}

int enc[15][1<<15];

void init2(int R, int C, int N) {
  int num = 0;
  REP(i,C) {
    int perm[N];
    REP(j,N) {
      if (j<N-R*i) perm[j] = 0;
      else perm[j] = 1;
    }
    do {
      int S = 0;
      REP(j,N) if (perm[j]) S |= 1<<j;
      enc[i][S] = num++;
    } while(next_permutation(perm,perm+N));
  }
}

// S:始点との接続状態
// T:セル同士の接続状態
// 流れるなら流れた状態にする
void func(int &S, int &T) {
  bool f = 0;
  REP(i,3) if ((T>>i&1) && (S>>i&1)) f = 1;
  if (f) REP(i,3) if (T>>i&1) S |= 1<<i;
}

int encode(int S, int T) {
  if (S==0) return 0;
  if (S==1 && T==6) return 7;
  if (S==2 && T==5) return 8;
  if (S==4 && T==3) return 9;
  return S-1;
}

// pii decode(int x) {
//   if (x==7) return pii(1,6);
//   if (x==8) return pii(2,5);
//   if (x==9) return pii(4,3);
//   return pii(x+1,0);
// }

ll memo[40000][10][1<<3];
int R, C;
int N;

int pnum[12];
int pkind[15];
int pmp[12][15];

ll solve(int x, int U, int S, int T, int Q);

ll dfs(int x, int U, int S, int T, int Q, int NU, int num, int id) {
  if (id == 12) {
    if (num == R) {
      int k = 0;
      int perm[3] = {};
      REP(i,N) {
        if (NU>>i&1) {
          perm[k++] = pkind[i];
        }
      }
      // if (x == 2) {
      //   cout << "x = " << x << endl;
      //   REP(i,num) cout << perm[i] << " "; cout << endl;
      //   cout << bitset<9>(U) <<" " << bitset<3>(S) << " " << bitset<3>(T) << " " << bitset<3>(Q) << endl;
      // }
      ll res = 0;
      do {
        int nS = 0;
        int nT = 0;
        int nQ = 0;
        REP(i,R) {
          if ((Q>>i&1) && table[perm[i]][3]) {
            if (S>>i&1) nS|=1<<i;
            if (T>>i&1) nT |= 1<<i;
          }
          if (table[perm[i]][1]) nQ |= 1<<i;
        }
        //assert(__builtin_popcount(nT) == 0);
        if (__builtin_popcount(nT) == 1) nT = 0;
        if (connect[perm[0]][perm[1]][2]) nT |= 3;
        if (connect[perm[1]][perm[2]][2]) nT |= 6;
        
        if (x == 0) nS |= 1;    // 1列目の1行目は始点
        
        func(nS,nT);
        if (nS) {
          res += solve(x+1, U|NU, nS, nT, nQ);
        }
      } while(next_permutation(perm, perm+R));
      return res;
    } else return 0;
  }
  ll res = 0;
  
  int pct[12] = {};
  REP(i,N) {
    if (U>>i&1) {
      pct[pkind[i]]++;
    }
  }
  REP(i,R-num+1) {
    if (pct[id]+i <= pnum[id]) {
      int UU = NU;
      REP(j,i) UU |= 1<<pmp[id][pct[id]+j];
      res += dfs(x,U,S,T,Q,UU, num+i, id+1);
    } else break;
  }
  return res;
}

ll solve(int x, int U, int S, int T, int Q) {
  if (x == C) {
    // cout << "x = " << x << endl;
    // cout << bitset<9>(U) <<" " << bitset<3>(S) << " " << bitset<3>(T) << " " << bitset<3>(Q) << endl;

    return (S>>(R-1)&1);
  }
  //cout << x << " " << bitset<15>(U) << " "<< enc[x][U] << endl;
  assert(enc[x][U] >= 0);
  int p = encode(S,T);
  ll &r = memo[enc[x][U]][p][Q];
  if (r >= 0) return r;
  
  return r = dfs(x,U,S,T,Q,0,0,0);
}
  
int main() {
  init();
  cin >> R >> C;
  REP(i,12) cin >> pnum[i];
  if (R>C) {
    swap(R,C);
    swap(pnum[1],pnum[2]);
    swap(pnum[3],pnum[5]);
    swap(pnum[7],pnum[8]);
    swap(pnum[9],pnum[10]);
  }
  N = 0;
  REP(i,12) {
    REP(j,pnum[i]) {
      pkind[N] = i;
      pmp[i][j] = N;
      N++;
    }
  }
  // assert(R<=3);
  // assert(N<=15);
  memset(enc,-1,sizeof(enc));
  init2(R,C,N);
  memset(memo,-1,sizeof(memo));
  cout << solve(0,0,0,0,0) << endl;
}
```