問題文

高橋君は、古き良き格闘ゲームで遊んでいます。

このゲームでは、A と B の 2 種類のボタンを使います。ボタン A を押すと、 高橋君の操作するキャラクターは敵キャラクターに攻撃を加えます。k-1 回連続でボタン A を押した後にボタン A を押したとき、 敵キャラクターには k のダメージが加わります。 ボタン B を押すと、高橋君の操作するキャラクターは格好いいポーズを取ります。この操作では、敵キャラクターにはダメージは加わりません。

このゲームは非常に単純なので、高橋君はこのゲームの最適戦略を完璧に理解してしまいました。 すなわち、ボタン A だけを押し続けるのが最も良い、ということです。 しかしこれでは面白くないので、高橋君はキャラクターの見た目を重視した、次のような戦略をとることにしました。 高橋君は A と B のみからなる文字列 S を用意し、以下を N 回繰り返します。

• |S| 回ボタンを押す。i 回目には、S の i 文字目が A ならボタン A を、B ならボタン B を押す。

すべての操作を終えた後に、敵キャラクターに加わったダメージの合計値を求めてください。

制約

• 1 ≦ |S| ≦ 10^5
• 1 ≦ N ≦ 2 \times 10^4
• S は A と B のみからなる。

入力例 1

3
ABBAA

出力例 1

16

高橋君は ABBAAABBAAABBAA の順にボタンを押します。ボタンAを押したとき、ダメージは順に 1,1,2,3,1,2,3,1,2 だけ加わります。

入力例 2

4
ABBAAABBAA

出力例 2

46

入力例 3

100
AAABAAAABAAAAABBBBBBBBBAABBBBBBAAAAABBB

出力例 3

4900

問題文

あなたは異世界で店舗経営をするシミュレーションゲームで遊んでいます。この異世界では、四則演算を含む数式の表現方法が通常のものと異なるようです。

ふつう数式を書くときは、四則演算は演算子を中置する 1+2+3 や 10/5 といった形で表しますが、この世界では四則演算を関数呼出しのような形で表します。たとえば、さきほどの例に対応する数式は +(1,2,3) や /(10,5) となります。

より厳密に言うとこの世界での数式は、単なる数字の列か、もしくは演算子 (+, -, *, / のいずれか) の直後で括弧 (() を開き、その中に数式をいくつかカンマ (,) で区切って並べ、その後括弧 ()) を閉じるという形式で表されます。ここで、括弧の中に現れる数式の個数は、加算と乗算 (+, *) のときは 1 つ以上ならいくつでも構いませんが、減算と除算 (-, /) のときは必ず 2 個です。

たとえば、0123 や +(10,*(20,30),-(40,50)) や *(5) はいずれも正しい数式です。いっぽう、+((1)) や -(5) といった文字列は正しい数式ではありません。

異世界の数式を表す文字列 S が与えられたとき、それを通常の (中置記法の) 数式に変換するプログラムを作成してください。ただし、変換後の数式は以下の条件を満たす必要があります。

• 変換後の数式における括弧は、変換前の括弧と対応する箇所にだけちょうど現れる必要があります。たとえば、+(1,-(2,3)) は (1+(2-3)) と変換し、*(5) は (5) と変換しなければなりません。
• 入力中に現れる数は先頭の 0 なども含めてそのまま出力せねばなりません。
• 余計な空白を入れてはいけません。たとえば、+(1,2) を (1 + 2) のように変換してはならず、(1+2) とする必要があります。

これらの条件について、より詳細には入出力例も参照してください。

制約

• 1 \leq |S| \leq 10^5
• 文字列 S は演算子 (+, -, *, /)、括弧 ((, ))、カンマ (,)、数字のみからなる、異世界の数式として正しい文字列である。

入力例 1

*(*(0,5),+(14,3),-(5,77))

出力例 1

((0*5)*(14+3)*(5-77))

入力例 2

+(1,+(+(2,3)),+(4,+(5)))

出力例 2

(1+((2+3))+(4+(5)))

括弧の位置と個数に十分注意してください。

入力例 3

9876

出力例 3

9876

入力例 4

+(123456789,12345678901234567890,0,00,000,0123456789)

出力例 4

(123456789+12345678901234567890+0+00+000+0123456789)

数式中に現れる数に明示的な上限はありません。また、数を表記する際に、先頭が 0 であるような表記法も正しいとされていること、およびそのように表記された数はそのまま出力せねばならないことにも注意してください。

入力例 5

*(5)

出力例 5

(5)

問題文

あなたは大人気ゲーム 「スペースエクスプローラー高橋君」 で遊んでいます。 このゲームの目的は宇宙船すぬけ号の艦長である高橋君となって、宇宙一の探検家を目指すことです。 現在あなたは 宇宙で一番おいしいりんご が宙域 RNG-58 にあることを突き止め、 RNG-58 へ向かっています。
宇宙で一番おいしいりんごは宇宙一おいしいので、宇宙海賊の青木君がすぬけ号を狙ってやってきました。 青木君は宇宙船けぬす号(すぬけ号の同型艦です)の艦長であり、高橋君のライバルです。 すぬけ号に取り付けられたすぬけキャノンでけぬす号を撃破しましょう！

けぬす号は 1 番から N 番までの番号がついた N ヶ所の区画からなり、区画 i の防御力は a_i です。 すぬけ号に取り付けられたすぬけキャノンは N 門あり、1 番から N 番までの番号がついています。 i 番のすぬけキャノンでけぬす号の区画 j を破壊するには a_j + (j-i)^{2} だけエネルギーを消費します。

どこか 1 つの区画を破壊すればけぬす号を撃破可能ですが、あなたは今後の航行のためにもなるべくすぬけ号のエネルギーを温存したいです。 それぞれのすぬけキャノンについて、けぬす号を撃破するのに最小限必要なエネルギーを求めてください。

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq a_i \leq 10^{12}
• 入力はすべて整数である

入力例 1

3
1 3 2

出力例 1

1
2
2

入力例 2

11
1 3 6 10 15 18 15 10 6 3 1

出力例 2

1
2
4
7
10
14
10
7
4
2
1

入力例 3

12
10 14 64 20 24 12 12 21 30 44 29 2

出力例 3

10
11
14
16
13
12
12
13
11
6
3
2

問題文

――世界に散らばる石板を集めよ。混沌の内に順序を与えよ。さらば、光はあたえられん――

高橋君の、パズル RPG 「Chaos of the Snuke World」のプレイは、今やクライマックスに差し掛かろうとしています。

このゲームの舞台は、遠い昔に魔法文明の栄えた帝国です。今から千二百年前、恐怖政治を敷いた時の皇帝に対するクーデターにより、市民が政権を掌握しました。 彼らは、今後このような権力者が誕生しないように、皇帝の権力の源であった魔法の石板を各地に分散させることにしました。しかし皮肉なことに、まさにこのことによって 魔力による国の結束に綻びが生じ、中央も地方も見境なく滅び、そして石板の置かれた場所も忘れ去られてしまいました。

主人公は、豊かだった魔法帝国の復活を夢見る少年です。高橋君の操作するこの少年は、各地の村を、森を、洞窟を巡り、ついに石板をすべて集めたのでした。

石板は全部で N 枚あり、i 個目の石板の表には整数 A_i が、裏には整数 B_i が書かれています。

さて、古都に戻ってきた少年のするべきことは、あとは廃墟と化した宮廷の最奥にある台に石板を並べることだけです。しかしここに、最後にして最大の難関があるのでした。

台には石板を横一列に並べることができます。少年は、台に石板を自由な順番で、どちらかの面を上にして並べることができます。少年が石板をすべて並べ終わると、 政権を建てた市民らのかけた古代の呪いが発動し、石板の裏表をひっくり返してしまうことがあるのです。どの位置の石板も、ちょうど半分の確率でひっくり返されてしまいます。

その後少年は、隣り合う石板同士を入れ替える操作を何度でも行うことができます。少年が石板を、上の面に書かれた整数が左から広義単調増加になるように並べることができたなら、 人々が豊かに暮らした帝国は復活し、少年の夢は叶うのです。しかし、もしこの操作に手間取ってしまえば……古代魔法が発動し、石板は再び散逸してしまうのです！

石板が散逸してしまえば、少年は再び石板を集めなおさなければなりません。早くゲームをクリアしたい高橋君は、隣り合う石板同士を入れ替える操作の必要回数の期待値が 最小になるように、石版を台に並べていくことにしました。

高橋君はゲームのやりすぎで、目が疲れています。高橋君のために、操作の必要回数の期待値の最小値を 2^N 倍した値(この値は整数であることが証明できます)を 10^9+7 で割ったあまりを求めてください。

制約

• 1\leq N\leq 10^5
• 1\leq A_i,B_i\leq 2N(1\leq i\leq N)
• 入力はすべて整数である

入力例 1

4
1 5
2 6
8 2
3 4

出力例 1

36

4,1,2,3 番目の順に石板を並べたとき、操作の必要回数の期待値は 2.25 になります。この 2^4 倍である 36 を出力します。

入力例 2

6
3 8
10 2
1 5
9 9
12 7
2 4

出力例 2

224

問題文

高橋君は、コンピュータを相手に海戦ゲームで遊んでいます。このゲームでは、ステージによって敵の船の種類が変わっていきます。 高橋君は、イカダステージ、カヌーステージ、帆船ステージ、高速ガレー船ステージ、戦艦ステージ、空母ステージを攻略し、ついに最終の潜水艦ステージに到達しました。

ゲームは、海域に見立てた H\times W のグリッド上で行われます。敵の潜水艦は、グリッドのマスのうちのいくつかに潜んでいます。同じマスに複数の潜水艦が潜んでいることはありません。

高橋君は探知機を用いて、各列に潜んでいる敵の潜水艦の隻数を知ることができました。i 列目に潜んでいる潜水艦は、合計で A_i 隻です。

さて、高橋君は爆雷を H 個持っています。爆雷は各行に上の行から順に 1 個ずつ投射することができます。行ごとに、高橋君は整数を指定します。 もしその行に潜んでいる敵の潜水艦の隻数が、その行に対して高橋君の指定した整数に等しいなら、高橋君はその行の潜水艦をすべて爆破することができます。 そうでない場合、その行の潜水艦を爆破することはできません。

高橋君は、すべての行の潜水艦をすべて爆破することのできる可能性のあるような整数の組の指定の仕方が何通りあるかが気になっています。 高橋君にかわって、そのような指定の仕方、すなわち各行に潜んでいる潜水艦の隻数の(整数 H 個からなる)組が何通りあるか求め、その値を 10^9+7 で割った値を求めてください。

制約

• 1 \leq H,W \leq 40
• 0 \leq A_i \leq H(1\leq i\leq W)
• 入力はすべて整数である

入力例 1

4 2
1
3

出力例 1

13

条件を満たす整数の組は、(0,1,1,2),(0,1,2,1),(0,2,1,1),(1,0,1,2),(1,0,2,1),(1,1,0,2),(1,1,2,0),(1,2,0,1),(1,2,1,0),(2,0,1,1),(2,1,0,1),(2,1,1,0),(1,1,1,1) の 13 通りです。

入力例 2

3 4
3
2
1
0

出力例 2

7

入力例 3

10 10
3
1
4
1
5
9
2
6
5
3

出力例 3

281268070

問題文

あなたは、RPG ゲームで遊んでいます。 このゲームでは、あなたは、勇者高橋くんとして人間界から魔法界に渡り、魔王と戦うことになります。 あなたは高橋くんの魔法の力を鍛え、ついに魔王を倒しました。 人間界と魔法界、ふたつの世界に平和が訪れましたが、これで物語が終わったわけではありません。 高橋くんは魔法界から人間界に帰還する必要があります。

魔法界と人間界をつなぐ通路は、1, 2, ..., N の番号がつけられた N 枚の扉と 1 つの魔法陣からなります。 魔法界から人間界に移動するためには、これら N 枚の扉を番号順に 1 回ずつ通り、その後魔法陣に入る必要があります。

魔法界には、魔法の帽子という特殊な帽子があります。 魔法界と人間界をつなぐ通路を通る際には、ちょうど 1 枚の扉を魔法の帽子をかぶって通り、それ以外のすべての扉を魔法の帽子をかぶらずに通る必要があります。

魔法界にいる人はそれぞれ魔法エネルギーを持っており、その大きさは通路の扉を通ることで後述のように変化します。 魔法陣に入る際には、安全のため、持っている魔法エネルギーの大きさは L 以上 R 以下となっている必要があります。

通路の扉を通った際の魔法エネルギーの大きさの変化は以下のとおりです。 大きさ x の魔法エネルギーを持つ人が扉 i を通ったとき、 通った後にその人が持つ魔法エネルギーの大きさ y は、 x, i の値およびその人が魔法の帽子をかぶっていたかどうかに応じて、

• 魔法の帽子をかぶっていなかった場合、
  • x < i ならば y = x + i
  • x \geq i ならば y = x - i
• 魔法の帽子をかぶっていた場合、x とi の大小関係によらず、y = x + i

となります。

高橋くんは、持っている魔法エネルギーの大きさが 0 の状態で、魔法の帽子を持って、魔法界と人間界をつなぐ通路に入りました。 魔法の帽子をかぶって通る扉の番号の選び方は N 通りありますが、このうち安全に魔法陣に入ることができる選び方は何通りあるか求めてください。

制約

• 1 \leq N \leq 10^{18}
• 0 \leq L \leq R \leq 10^{18}

入力例 1

3 5 7

出力例 1

1

扉 1 または扉 2 を通る際に魔法の帽子をかぶった場合、魔法エネルギーの大きさは 0 \rightarrow 1 \rightarrow 3 \rightarrow 0 と 変化します。 これらの扉を魔法の帽子をかぶって通る扉として選んだ場合、条件を満たしません。

扉 3 を通る際に魔法の帽子をかぶった場合、魔法エネルギーの大きさは 0 \rightarrow 1 \rightarrow 3 \rightarrow 6 と変化します。 この扉を魔法の帽子をかぶって通る扉として選んだ場合、条件を満たします。

以上より、条件を満たす帽子のかぶり方は 1 通り存在します。

入力例 2

5 67 89

出力例 2

0

入力例 3

1357 500 5000

出力例 3

1354