I - Flip Cards [TGC Edition]

配点： 点

から までの番号がついた 枚のカードが一列に並んでいて，カード とカード とが隣り合っています．()
カード の表に整数 が，裏に整数 が書かれています．
また，はじめ全てのカードは表向きです．

MojaMoja 君は次の条件をいずれも満たすようにカードを裏返します：

• 表を向いたカードが 枚より多く連続しない．
• 裏を向いたカードが 枚より多く連続しない．

このとき， 枚のカードの向いている面に書かれた整数の総和を，その裏返し方のスコアとします．
条件を満たすような全ての裏返し方におけるスコアの総和を求めてください．

ただし，答えは非常に大きくなる場合があるため， で割ったあまりを答えてください．

• 入力はすべて整数

各テストケースの入力は，それぞれ以下の形式で与えられる：

答えを出力せよ．

1
5 2
3 4 5 7 5
2 3 1 4 2

120

カードの表を +，裏を - として表すと，ありうるカードの裏返し方は + - - + -，+ - + - -，+ - + - +，- - + - -，- - + - +，- + - - +，- + - + - の 通りです．
これらのスコアはそれぞれ ですから，これらの総和である (を で割ったあまり) を答えればよいです．

3
5 1
1 2 3 4 5
5 4 3 2 1
5 100
1 2 3 4 5
1 2 3 4 5
5 3
0 0 0 0 0
0 0 0 0 0

30
195
0