Problem: Have you ever heard of Moduic Squares? They are like 3 × 3 Magic Squares, but each of them has one extra cell called a moduic cell. Hence a Moduic Square has the following form.

<image>

Figure 1: A Moduic Square

Each of cells labeled from A to J contains one number from 1 to 10, where no two cells contain the same number. The sums of three numbers in the same rows, in the same columns, and in the diagonals in the 3 × 3 cells must be congruent modulo the number in the moduic cell. Here is an example Moduic Square:

<image>

Figure 2: An example Moduic Square

You can easily see that all the sums are congruent to 0 modulo 5.

Now, we can consider interesting puzzles in which we complete Moduic Squares with partially filled cells. For example, we can complete the following square by filling 4 into the empty cell on the left and 9 on the right. Alternatively, we can also complete the square by filling 9 on the left and 4 on the right. So this puzzle has two possible solutions.

<image>

Figure 3: A Moduic Square as a puzzle

Your task is to write a program that determines the number of solutions for each given puzzle.



Input

The input contains multiple test cases. Each test case is specified on a single line made of 10 integers that represent cells A, B, C, D, E, F, G, H, I, and J as shown in the first figure of the problem statement. Positive integer means that the corresponding cell is already filled with the integer. Zero means that the corresponding cell is left empty.

The end of input is identified with a line containing ten of -1’s. This is not part of test cases.

Output

For each test case, output a single integer indicating the number of solutions on a line. There may be cases with no solutions, in which you should output 0 as the number.

Example

Input

3 1 6 8 10 7 0 0 2 5
0 0 0 0 0 0 0 0 0 1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1


Output

2
362880

Solution (in CPP):

Solution:
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
#include <complex>
#include <assert.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <double,double> P;
 
static const int tx[] = {+0,+1,+0,-1};
static const int ty[] = {-1,+0,+1,+0};
 
static const double EPS = 1e-8;

int table[3][3];

bool check(int mod){
  set<int> result;
  for(int y = 0; y < 3; y++){
    int sum = 0;
    for(int x = 0; x < 3; x++){
      sum += table[y][x];
    }
    result.insert(sum % mod);
  }
  for(int x = 0; x < 3; x++){
    int sum = 0;
    for(int y = 0; y < 3; y++){
      sum += table[y][x];
    }
    result.insert(sum % mod);
  }
  result.insert((table[0][0] + table[1][1] + table[2][2]) % mod);
  result.insert((table[0][2] + table[1][1] + table[2][0]) % mod);
  return (result.size() == 1);
}

int dfs(int pos,int used,int mod){
  if(pos >= 9 && check(mod)){
    return 1;
  }
  else if(pos >= 9){
    return 0;
  }
  int res = 0;
  int x = pos % 3;
  int y = pos / 3;

  if(table[y][x] == 0){
    for(int i = 1; i <= 10; i++){
      if(used & (1<<i)) continue;
      table[y][x] = i;
      res += dfs(pos + 1, used | (1<<i),mod);
      table[y][x] = 0;
    }
  }
  else{
    res += dfs(pos + 1, used,mod);
  }
  return res;
}

int main(){
  while(~scanf("%d",&table[0][0])){
    int used = 0;
    if(table[0][0] != 0){
      used |= (1<<table[0][0]);
    }

    for(int y = 0; y < 3; y++){
      for(int x = 0; x < 3; x++){
        if(y == 0 && x == 0) continue;
        scanf("%d",&table[y][x]);
        if(table[y][x] != 0){
          used |= (1<<table[y][x]);
        }
      }
    }
    int mod;
    scanf("%d",&mod);
    if(mod == -1) break;

    used |= (1<<mod);
    int res = 0;
    if(mod == 0){
      int prev = used;
      for(int i = 1; i <= 10; i++){
        if(used & (1<<i)) continue;
        used |= (1<<i);
        mod = i;
        res += dfs(0,used,mod);
        used = prev;
      }
    }
    else{
      res += dfs(0,used,mod);
    }
    printf("%d\n",res);
  }
}