Evaluate All

長さの,自然数ないしは記号のみから構成される文字列が与えられる.(要素間は空白区切り)

なお,は順に加算,減算,乗算の演算子であるものとする.

全ての連続部分列(全てで個)に対して以下の評価値を求め,その総和をで割ったあまりを求めよ.

その文字列を逆ポーランド記法として評価した際

・正しい評価式であるならば得られる演算結果

・不正な評価式であるならば0

・

・文字列の要素について以下が成り立つ.

・数値である場合をみたす.

・文字列である場合それはのいずれかである.

入力は以下の形式で与えられる.

N
c1 c2 ... c_N

全ての連続部分文字列に対しての評価値(上記参照)を求め

その総和をで割ったあまりを求めよ.

ただし,数字つから構成される文字列は有効な記法と解釈することに注意せよ.

7
3 1 + 4 1 - *

28

考えうる部分列のうち,逆ポーランド記法として評価したとき有効なものは全てでつ存在し, その全てについて評価値を計算すると以下のようになる.

したがって,その総和であるを出力する.

9
+ - * + - * - - *

0

この場合,全ての部分列が誤りである.

3
* * 4

4

この場合,有効な評価式はだけである.

22
3 1 4 1 * 5 - 9 2 6 * 5 3 * 5 - 8 * 9 7 - 9

199

10
3 1 * 4 15926535 * 8 + 979 *

234632921

で割ったあまりを求めることに注意.