Problem Description

kuro又又又又在买巧克力！

kuro买了一个巧克力礼盒，礼盒共有n层，其中第i层有i块巧克力（左对齐），首先，kuro会吃掉第一层的第一块巧克力，接下来，kuro可以吃掉其正下方的那块巧克力，或者吃掉其右下方的那块巧克力，直到下方没有巧克力，形式化的说，假设kuro在当前吃掉了第i层的第j块巧克力，接下来可以选择吃掉第i+1层的第j或j+1块巧克力，直到第n层。

每一块巧克力都有自己的美味值，设kuro吃掉的巧克力序列的美味度为$c_i(1 \leq i \leq n)$,则kuro得到的满意度为$\prod_{i=1}^{n} 2^{c_i}$,即$2^{c_i}$的积。

kuro希望最大化满意度，请你告诉她可以得到的最大满意度是多少？

考虑到这个数很大，你只需要输出其对 998,244,353取模后的值即可。

Input Format

第一行一个整数 $n$ 。

接下来 $n$ 行，第 $i$ 行包含 $i$ 个整数，表示 $(a_{i,1},a_{i,2},\dots,a_{i,i})$，表示每块巧克力的美味度。

Output Format

输出一个整数，表示可以获得最大满意度对 998,244,353 取模的值。

Sample

输入 1

3
1
2 3
4 5 6

输出 1

1024

解释

最佳路径为 $(1 \rightarrow 3 \rightarrow 6)$，其满意度为 $(S_{\max}=1+3+6=10)$。 答案为 $(2^{10}\bmod 998244353=1024)$。

输入 2

1
32

输出 2

301989884

Hint

• $(1 \le n \le 2000)$
• $(0 \le a_{i,j} \le 10^9)$