A. 112358
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

$$$112358$$$ is a team from Hunan University that participated in this year's ICPC WuHan station.

Why this name? Because zmy is very fond of playing a game called $$$112358$$$.

The rules of the game are as follows:

There are a total of 16 squares, and each move can shift the tiles up, down, left, or right. If two adjacent numbers satisfy the condition that they are consecutive terms in the $$$\bf{Fibonacci\ sequence}^\dagger$$$, they will merge into their sum, and the score increases by the value of the new number.

After each move, you can either add a new number $$$1$$$, or not add at all. Note that the newly added $$$1$$$ is not included in the total score.

Now, given a current board state of the $$$112358$$$ game, you are asked to output the current score modulo 998244353.

$$$^\dagger$$$ The Fibonacci sequence is defined as

$$$$$$F_1 = 1,\ \ \ F_2 = 1,\ \ \ F_i = F_{i-1} + F_{i-2} \ \text{for all } i \ge 3.$$$$$$

The first $$$10$$$ terms are $$$[1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55].$$$

Input

$$$4$$$ rows and $$$4$$$ columns, totaling $$$16$$$ numbers $$$a_{i,j}\ (0 \le a_{i,j} \le 10^6)$$$, indicating that the element in the i-th row and j-th column is $$$F_{a_{i,j}}$$$.

Specifically, $$$a_{i,j}=0$$$ means the current position is empty.

Output

One line with a number — the current score, modulo $$$998244353$$$.

Example
Input
1 2 0 0
0 0 0 0
3 4 0 1
0 0 6 0
Output
32
Note

1. The real current board state is shown below:

$$$1$$$$$$1$$$$$$0$$$$$$0$$$
$$$0$$$$$$0$$$$$$0$$$$$$0$$$
$$$2$$$$$$3$$$$$$0$$$$$$1$$$
$$$0$$$$$$0$$$$$$8$$$$$$0$$$

 Some examples about the rule of points:

  • When you want to get a number $$$3$$$, there must be two adjacent numbers $$$1$$$ and $$$2$$$, then you combine them into number $$$3$$$, and get $$$3$$$ points.

  • When you want to get a number $$$21$$$, there must be two adjacent numbers $$$8$$$ and $$$13$$$, then you combine them into number $$$21$$$, and get $$$21$$$ points.
$$$~\\$$$

2. In this problem, $$$a$$$ modulo $$$p$$$ refers to taking the remainder of $$$a$$$ after division by $$$p$$$. For example:

  • $$$11$$$ modulo $$$5 = 1$$$ ($$$11 = 5\times 2 + 1$$$);
  • $$$7$$$ modulo $$$5 = 2$$$ ($$$7 = 5\times 1 + 2$$$);
  • $$$3$$$ modulo $$$5 = 3$$$ ($$$3$$$ is already smaller than $$$5$$$).