You are given a 3-dimensional integer array of size .
Initialize the following variables:
integer x = 0;
integer w = 1;
stack s = {};
Then, for each , choose an integer such that and do the following action:
If , do the following:
w *= A[t][x][y];
s.push(x);
x = y;
The above denotes .
If , do the following:
assert (!s.empty());
w *= A[t][x][s.top()];
x = (x + s.top()) % N;
s.pop();
You can't choose if the stack is empty before the action.
Note that the stack has the following operations:
push(x): adds an element to the collection.
pop(): removes the most recently added element.
top(): returns the value of the most recently added element.
For each , consider all possible sequences such that the final value of is . Compute the sum of the corresponding values of over all such sequences, and output the result modulo .
输入格式
The input is given in the following format:
means the value of .
All input values are integers.
输出格式
Output lines. On the -th line (), output the answer for .
