U141362 矩阵乘法

自从上次小明从你的矩阵快速幂程序得到了两个序列的 $F_n$，他就对矩阵运算有了兴趣，现在他在研究矩阵乘法。 现在他正在写一条矩阵链的乘积问题，即有 $n$ 个矩阵 $A_i$，但是他发现程序运行得很慢，所以请你优化一下，看看可以优化到的最少运行乘法次数。

给出 $n$ 和 $n+1$ 个数 $p_0,p_1,...,p_n$，代表矩阵 $A_i$ 为 $p_{i-1}\times p_i$ 的规模。 现在你发现加括号可以减少乘法次数，请求出最少的运算次数对$10^{9}+7$取模的结果与加括号方式（不能改变矩阵顺序）。

输入共 $2$ 行。\ 第 $1$ 行有 $1$ 个整数 $n$。\ 第 $2$ 行有 $n+1$ 个整数 $p_i$。

输出共 $2$ 行。\ 第 $1$ 行输出 $1$ 个整数，为最少的运行乘法次数对$10^9+7$取模的结果。\ 第 $2$ 行输出一行字符串，包含`(` `)` `,` `1~n`，表示加括号方案，注意 $1$ 前和 $n$ 后也要加括号，如： $$(1,(2,(3,(4,(5,((6,7),(8,(9,10))))))))$$

$1\leqslant n\leqslant 5000,1\leqslant p_i\leqslant 10^9+7$