問題


長さ の数列 が与えられます

要素数が () であって、 各要素が であるような 個の狭義単調増加数列 について を求め、その総和を で割ったあまりを求めなさい

より直感的には数列  個の隣接要素の間に または を挿入し、 における計算が における計算より優先されるものとして計算した時の総和を で割ったあまりを求めなさい

制約



入力例1


3
1 2 3

出力例1


26

です。

提出


Go (1.14)