题目大意

若干个矩阵连乘, 请计算出所需的最小计算量.

两矩阵相乘时, 第一个矩阵的列数必须等于第二个矩阵的行数. 所得新矩阵行数为第一个矩阵的行数, 列数为第二个矩阵的列数. 如$A_{p\times r}B_{r\times q}$可得$C_{p\times q}$, 这一操作花费的计算量为$pqr$.

矩阵连乘符合分配律而不符合交换律, 即$(AB)C=A(BC)$, 但$AB\neq BA$.

输入

首行输入一个整数$n$, ($2\leq n\leq 10$), 表示正在计算$n$个矩阵的连乘.

接下来$n$行, 每行给出一个数对$p_i$, $q_i$, ($p_i, q_i\leq 46340$), 分别表示第$i$个矩阵之列数与行数.

输出

输出一个整数, 即所需最小的计算量, 答案对$998244353$取模.

样例

2
2 2
2 2

8

5  
2 4
4 6
6 5
5 7
7 9

304