問題

背景

古典論理のプロであるノットさんは、二重否定を見つけたら直ちに除去してしまう。 あなたは、ノットさんの代わりに二重否定を除去するプログラムを書くことになった。

課題

英語小文字からなる複数の単語をちょうど一つずつのスペースで区切った文字列 S が一行で与えられる。 「not not (not以外の単語)という部分文字列が S に含まれ、それぞれのnotが単語であるならば、その部分文字列の先頭 8 文字not not を削除する」という操作を、S にnot not (not以外の単語)という部分文字列が含まれなくなるまで繰り返したときに得られる文字列 T を出力せよ。なお、このような操作を行える場所が S に複数含まれる場合があるが、どのような順番で操作を行っても最終的に同じ文字列 T が得られることが知られている。

配点

100

入力

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

S

文字列 S が一行で与えられる。

制約

• 1 ≤ |S| ≤ 5000
• S は英語小文字(a-z)とスペース( )のみからなる。
• S 中にスペースは連続して現れない。
• S の先頭および末尾はスペースではない。

出力

操作終了後に得られる文字列 T を 1 行で出力せよ。

入力例1

not not pro

出力例1

pro

入力例2

not not not

出力例2

not not not

notの後にnot以外の単語が続かない場合二重否定の除去は行われないことに注意せよ。

問題

背景

ビッグブリッジ伯爵は、UTPC2015を2015年中に開きたいと考えている。 忙しいビッグブリッジ伯爵は、テストデータの作成をあなたにお願いすることにした。

課題

2 次元平面上の 1 点が与えられるので、その点を交点とする 2 つの直線を求めよ。 求めた 2 つの直線は 2 つの異なる通過点を用いて表現せよ。ただし、通過点の座標はすべて絶対値が 10,000 以下の整数でなければならない。

配点

100

入力

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

x y

x, y はそれぞれ入力の点の x 座標と y 座標であり、ちょうど小数第 3 位まで与えられる。

制約

• |x|, |y| ≤ 1,000
• x, y は 1,000 倍すると整数になる値である。

出力

1 行目と 2 行目にそれぞれ 1 本目と 2 本目の直線の通過点となる頂点の座標を出力せよ。 各行は1つの半角スペースで区切られた 4 つの整数からなるようにし、前半 2 つと後半 2 つをそれぞれ異なる通過点の座標とせよ。 座標は x 座標と y 座標をこの順で並べること。 x 座標と y 座標は絶対値が 10,000 以下の整数でなければならない。 条件を満たす出力が複数考えられることがあるが、この場合はいずれの出力でも正解となる。

入出力例

入力例 1

0.000 0.000

出力例1

0 0 1 0
0 0 0 1

入力例 2

0.001 0.001

出力例2

0 0 1 1
0 1 1 -998

問題

背景

グラフ塗り職人のイクタ君は、顧客の要望にできるだけ忠実に色を塗るため、グラフの塗り方について日々研究をしている。 今日は、頂点を二色に塗りわけた時、両端の頂点の色が異なる辺の数に注目することにした。

課題

n 個の頂点と n 本の辺からなる連結なグラフが存在する。このグラフには両端が同じ頂点に繋がっている辺は存在せず、またある 2 つの頂点の間に複数の辺が存在することも無い。

このグラフのすべての頂点を赤色または青色に塗る。この時、赤色に塗られた頂点も青色に塗られた頂点も一つ以上存在するようにする。そのような条件を満たすように塗った時の、両端の頂点が別々に塗られている辺の数の最小値と最大値をそれぞれ求めよ。

なお、この問題はグラフの最小カットおよび最大カット (日本語版 Wikipedia) を求める問題と同値である。

配点

100

入力

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

n
a_1 b_1
:
a_n b_n

1 行目に頂点および辺の数 n (3 ≤ n ≤ 100,000) が書かれている。 2 行目から n+1 行目には、2 つの整数 a_i, b_i が書かれていて、頂点 a_i と頂点b_i を結ぶ辺が存在することを表している。

制約

• 3 ≤ n ≤ 100,000
• 1 ≤ a_i,b_i ≤ n
• 両端が同じ頂点に繋がっている辺は存在しない。
• ある2つの頂点の間に複数の辺は存在しない。

出力

両端の頂点が別々に塗られている辺の数の最小値 min と最大値 MAX を空白区切りで 1 行に出力せよ。

入出力例

入力例1

4
1 2
2 3
3 1
1 4

出力例1

1 3

問題

背景

音楽ゲームが好きなビッグブリッジ伯爵は、ある音楽ゲームをクリアしたいと思っている。 幸いにも、そのゲームにおいて、どのタイミングでどこをタッチすればよいのかは分かっているが、ビッグブリッジ伯爵には自分のスキルで実際にクリアすることができるかどうかがわからない。 そこであなたは、ビッグブリッジ伯爵がその音楽ゲームをクリアすることができるかどうかを調べてあげることにした。

課題

ビッグブリッジ伯爵が音楽ゲームで使うことのできる指の数 m と各指の初期位置 (rx_i, ry_i) が与えられる。 また、音楽ゲームにおいてタッチすべき場所とタイミングが n 個与えられる。 この音楽ゲームをクリアするためには、各 i (1 ≤ i ≤ n) に対して、2 次元平面上の (px_i, py_i) の位置をどれか 1 つ以上の指で時間 s_i から t_i の間、ずっとタッチし続ける必要がある。 さらに、この音楽ゲームでは各場所をタッチすべきタイミングが連続している。 つまり、各 i (1 ≤ i ≤ n - 1) に対して、t_i = s_{i+1} となっている。 ビッグブリッジ伯爵はそれぞれの指を独立に、1 単位時間あたりユークリッド距離で最大 1 の速度で任意の方向に動かすことができる。 ビッグブリッジ伯爵がこの音楽ゲームをクリアすることができるかどうかを判定せよ。

配点

200

入力

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

m
rx_1 ry_1
:
rx_m ry_m
n
px_1 py_1 s_1 t_1
:
px_n py_n s_n t_n

1 行目には、ビッグブリッジ伯爵が音楽ゲームで使うことのできる指の数を表す整数 m が与えられる。 続く m 行には、それぞれの指がゲームの開始時に置かれている位置を表す 2 つの整数 rx_1, ry_1 が空白区切りで与えられる。 m+2 行目には、音楽ゲームでタッチすべき場所の個数を表す整数 n が与えられる。 続く n 行には、それぞれのタッチすべき位置を表す 2 つの整数 px_i, py_i と、その位置をタッチすべきタイミングを表す 2 つの整数 s_i, t_i が空白区切りで与えられる。

制約

• 1 ≤ m ≤ 3
• 1 ≤ n ≤ 1,000
• 0 ≤ rx_i, ry_i ≤ 1,000
• 0 ≤ px_i, py_i ≤ 1,000
• 0 ≤ s_i < t_i ≤ 1,000
• 1 ≤ i ≤ n - 1 である各 i に対して、t_i = s_{i+1}

出力

ビッグブリッジ伯爵が音楽ゲームをクリアすることができる場合は YES を、そうでない場合は NO を 1 行に出力せよ。

入出力例

入力例 1

1
0 0
1
1 2 3 4

出力例 1

YES

入力例 2

2
0 0
0 10
3
1 2 3 4
2 3 4 7
5 2 7 8

出力例 2

NO

入力例 3

3
0 0
0 10
10 0
5
1 1 2 3
1 9 3 4
9 1 4 5
3 1 5 6
1 11 6 7

出力例 3

YES

問題

背景

働きたくない王国は働きたくない人間のための王国である。国民はいつも働かずに暮らす方法を考えている。そのため、宝くじはこの国で一番人気の高い娯楽となっている。

この国の宝くじは次のような仕組みになっている。 各くじにはくじ番号として 1 つの正の整数が書かれている。 いくつかの当選番号と当選金があり、それぞれの当選番号について、それを末尾に含むくじ番号を持つくじに、対応する当選金が支払われる。 例えば、当選番号が 100 で対応する当選金が 200 の場合はくじ番号が 100 や 2100 のくじに 200 の当選金が支払われる。

幸か不幸かこの国で一番の働き者であるあなたは、宝くじの当選発表の実況中継を担当することとなった。実況中継においては、当選番号と当選金が 1 つずつ発表され、そのたびに 1 つのくじで得られる当選金のうち理論上最も高い金額を発表する必要がある。

国民の宝くじに対する熱狂ぶりはすさまじく、実況中継の失敗は絶対に許されない。 そこで、この大仕事を正確にこなし、かつ中継本番中に家で寝ていられるようにするために、あなたは必要な値を求めるプログラムを書くことにした。

課題

宝くじの当選番号とその賞金が n 個与えられる。 i (1 ≤ i ≤ n) 番目の当選番号 a_i と賞金 b_i は整数で与えられ、a_i の桁数が m であるときに下 m 桁が a_i と一致している宝くじにその賞金 b_i が与えられる。 例えば当選番号が 100 のときは、下3桁が 100 であるような宝くじ、つまり番号が 100 の宝くじや 2100 の宝くじに賞金が与えられる。 各 i (1 ≤ i ≤ n) について、i 番目までの当選番号での賞金の合計額が最も多い宝くじの賞金の合計額を答えよ。

配点

200

入力

n
a_1 b_1
:
a_n b_n

制約

• 1 ≤ n ≤ 100,000
• 1 ≤ a_i ≤ 10^9
• 1 ≤ b_i ≤ 10^9
• a_i, b_i には leading zero が含まれないことに注意せよ。

出力

i 番目までの当選番号での賞金額の合計の最大値 c_i (1 ≤ i ≤ n) を i 行目に出力せよ。

入出力例

入力例1

4
11 100
1 10
10 150
21 200

出力例1

100
110
150
210

問題

背景

注意力散漫なビッグブリッジ伯爵はよく電話番号を書き間違えて大学の事務局に怒られている。何回も怒られてさすがに懲りた彼は、自分の書き間違えの傾向を調べた結果、隣接する 2 つの数字を入れ替えて書いてしまうことが非常に多いことがわかった。このミスを犯した時に彼がすぐに気がつけるよう、簡単に計算できる検査符号を設計してあげよう。

課題

10 桁の整数に対するチェックディジットを設計せよ。すなわち、次に示す 2 つの条件を満たす、10 桁の整数を入力とし 0 以上 100 未満の整数であるチェックディジットを出力する関数を設計せよ。ただし、入力の整数は 0 以上で、10^9 未満の整数についてはleading zeroを付けて、10 桁と見なす。

• 同一の入力に対して常に同じ出力を得る。
• 隣接する 2 数が異なる時、それを入れ替えて得た整数を入力とすると、元と異なる出力を得る。

配点

200

入力

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

T
a_1
:
a_T

1 行目にはチェックディジットをつける整数の個数 T が与えられる。 続く T 行にはチェックディジットをつける整数 a_i が 1 行ずつ与えられる。

制約

• 1 ≦ T ≦ 10^5
• a_i は 0 以上 10^{10} 未満の整数で、10 桁になるようにleading zeroが付けられている。
• a の要素は重複しうる、すなわち、i ≠ j である i, j に対して a_i = a_j となることがあることに注意せよ。

出力

入力で与えられたそれぞれの整数に対応するチェックディジットを出力せよ。

採点方式

この問題に対しては 8 つのテストケースが用意されており、それぞれ 25 点を満点として採点される。

それぞれのテストケースにおける T の値は次の通り。

• T = 30, 100, 300, 1000, 3000, 10000, 30000, 100000

各テストケースに対するジャッジの出力は次のようにして定める。

• つけたチェックディジットが問題文に示す2つの条件と矛盾するとき - WA
• つけたチェックディジットが問題文に示す2つの条件に矛盾しないとき - AC
• この時の得点は、出力に含まれるチェックディジットの種類数を k として、 min(25, max(8 - k, 0)^2) とする。

各テストケースは独立に採点される。特に、同じ整数値に対して異なるテストケースで異なるチェックディジットが付けられていてもただちに WA とはならない。

入力例1

6
0000000011
0000000012
0000000013
0000000021
0000000031
0000000011

出力例1

0
0
0
1
1
0

問題

背景

あなたは、あるバラエティ番組のプロデューサーである。この番組では、野球経験の無いアイドルの女の子たちが、バッティングセンターで剛速球を（予め定められた数）P 球のうち何球打ち返せたかを、出演者たちが予想する。

その際、単純にそれぞれのアイドルが何球打ち返せたかを予想するのではなく、アイドルの集合を選んで、その集合に含まれるアイドルの子たちの打ち返せた球の数の合計が予め定められたある数 X と一致していれば正解、ということにする。

現在、それぞれのアイドルが何球打ち返せたかという「バッティング結果」の収録を行っている。一部のアイドルは既に挑戦を終えた。その時あなたは、場合によっては「打ち返した球の合計が X となるような集合の選び方が複数存在する、または一つも存在しない」という状況になってしまうことに気が付いた。

そこで、残りのアイドル達の収録が終了したとき、「打ち返した球の合計が X となるような集合の選び方」が丁度 1 通りとなるような「バッティング結果」は何通りあるか求めよ。

課題

長さ n の整数列 a_i が与えられる。a の要素の一部は 0 以上 P 以下の整数を自由に選ぶことができる。この時、和がちょうど X になるような a の部分列の選び方がちょうど 1 通りになるような整数の選び方の数を 1,000,000,007 で割った余りを求めよ。ただし、部分列の選び方が等しいとは、その部分列をなす要素の添字の集合が等しいことのみを言うこととする。

配点

200

入力

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

n X P
a_1
:
a_n

1行目には、n、X、P の 3つの整数が書かれている。 続く n 行には a の要素が先頭から順に 1 行に 1 つずつ書かれている。? (疑問符) はその要素が自由に整数を選ぶことができるものであることを表している。

制約

• 1 ≤ n ≤ 50
• 1 ≤ X ≤ 10
• 1 ≤ P ≤ 10
• a_i = ? または 0 ≤ a_i ≤ P

出力

求める値を 1 行に出力せよ。

入出力例

入力例1

3 5 4
1
4
?

出力例1

2

入力例2

3 5 5
?
1
?

出力例2

15

問題

背景

この問題は凸多角形を回すだけです。がんばってください。

課題

この問題はリアクティブ形式の問題である。つまり、あなたは応答プログラムの出力を利用して解を求める必要がある。

y 軸正の方向を上、x 軸正の方向を右とする xy 平面上に、1 つの頂点が原点にあり、それ以外の頂点は y 座標が 0 未満の格子点上に存在する凸多角形がある。 この凸多角形の頂点数は 10 以下、頂点の座標は絶対値が 1,000 以下、内角は 170 度以下である。 あなたのプログラムは応答プログラムに対して、原点を中心に指定された角度だけ反時計回りに回転した凸多角形の頂点のうち最も大きな y 座標を尋ねることができる。 この質問を 1,000 回以内の任意の回数だけ用いて凸多角形のもとの座標を求めよ。

配点

300

入出力

あなたのプログラムは凸多角形をある角度 x （度数法による値）だけ反時計回りに回転させた時の頂点のうち最も大きな y 座標 y_{max} を尋ねることができる。 例えば、C/C++ で 12.3 度反時計回りに回転した時の y_{max} を質問するには、まず次のようにする。

printf("? 12.3\n"); fflush(stdout);

double ymax; scanf("%lf", &ymax);

凸多角形の座標を出力するときは、次のフォーマットにしたがって行う。

! n
! x_1 y_1
…
! x_n y_n

1行目には ‘!’ (感嘆符) と半角スペース 1 つに続き、凸多角形の頂点数 n を出力する。 2行目からn+1行目には ‘!’ (感嘆符) と半角スペース 1 つに続き凸多角形の頂点の座標を整数値で原点から順に反時計回りに出力する。あなたのプログラムは凸多角形の座標を終了したあと、ただちに終了しなければならない。

以下のときのジャッジ結果は不定である。

• 質問のフォーマットが正しくないとき
• 解答を出力するフォーマットが正しくないとき
• 解答を出力したあとであなたのプログラムがただちに終了しなかったとき

C/C++ 以外での入出力方法については、過去の AtCoder で出題されている問題 (リンク: ABC 019 D: 高橋くんと木の直径 ) を参考にしてもよい。

入出力例

問題

背景

趣味の盆栽に没頭しているイクタ君は、枝の切り方と肥料の与え方を工夫し、上手に盆栽を作ることが可能である。 イクタ君は肥料の与え方がとてもうまいので、特定の枝を太くしたり、細くしたりできる。 (この盆栽の枝は次元を超越しており太さが負になりうることに注意してほしい。)
また、ある盆栽が大きすぎると思った時はその盆栽の枝のうち最も細い(太さの値が最も低い)枝を切って、木を 2 つに分け、切り取って別れた木はまた鉢に植え、新たな盆栽とする。 あなたは、イクタ君が盆栽を育てる計画をもとに、枝を切る操作でどの枝を切るかを特定することにした。

課題

木が与えられる。木の辺にはそれぞれ整数の強度が与えられている。
この木に対して、次のクエリを処理せよ。

• クエリ1: 辺 i , 整数 d が与えられる。辺iの強度を d だけ増加させる。辺 i が既に削除されている場合は何もしない。
• クエリ2: 辺 i が与えられる。辺 i を含む連結成分を構成する辺のうち、一番強度の低い辺 j を一行で出力した後、辺 j を削除する(強度が最低のものが複数の場合は、辺の番号が最小のものを削除する。) 辺 i が既に削除されている場合は -1 を出力せよ。

配点

300

入力

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

N
a_1 b_1 c_1
:
a_{N-1} b_{N-1} c_{N-1}
Q
q_1
:
q_Q

入力の 1 行目に木の頂点数を表す整数Nが与えられる。
続く N-1 行に頂点 a_i, b_i とそれらを結ぶ辺の初期強度 c_i を表す 3 つの整数が与えられる。
N+1 行目に処理すべきクエリの数 Q 、続く Q 行にクエリの内容が以下のように書かれている
クエリ 1 は

1 i d

2 i

制約

• 2 ≤ N ≤ 100,000
• 1 ≤ a_i, b_i ≤ N
• -100,000 ≤ c_i ≤ 100,000
• 1 ≤ Q ≤ 100,000
• 1 ≤ i ≤ N-1
• -10,000 ≤ d ≤ 10,000
• 入力で与えられるグラフは木になっている。

部分点

この問題には部分点が設定されている。この問題のテストケースのうち 30 点分は追加で以下の制約を満たす。

• 2 ≤ N ≤ 1,000
• 1 ≤ Q ≤ 1,000

出力

クエリ2に対する答えをそれぞれ一行で出力せよ。

入力例1

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

出力例1

3
1
-1
4

入力例2

6
2 1 -2
3 2 0
4 1 -1
5 4 0
6 2 0
6
2 4
2 3
2 4
1 2 4
1 2 0
2 3

出力例2

1
3
4
-1

問題

背景

イクタ君は一列に並んだ看板の色がすべて同じ色になるように塗り替えようとしている。 一方、ビッグブリッジ伯爵はイクタ君の邪魔をするために、次々と看板を増やしたり減らしたりする。 それぞれの邪魔が行われた時点で塗り替えを始めると、すべての看板を同じ色にするのにどれだけ時間がかかるか求めよ。

課題

N(1 ≤ N ≤ 100,000) 個の看板が x 軸上に並んでいる。 i 番目の看板は x_i(-10^9 ≤ x_i ≤ 10^9) の位置にあり、a_i(1 ≤ a_i ≤ 200,000) の色で塗られている。 ビッグブリッジ伯爵は Q(1 ≤ Q ≤ 100,000) 回の看板の追加や削除を行う。 各追加と削除が行われた後にイクタ君が塗り替えを始めると、すべての看板を同じ色に塗り替えるのにどれだけ時間がかかるか求めよ。 イクタ君は最初 x = 0 の位置におり、x_p から x_q に移動するのには |x_p - x_q| の時間がかかる。 また、a_p の色の看板を a_q の色に塗り替えるのには |a_p - a_q| の時間がかかる。

配点

300

入力

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

N
x_1 a_1
:
x_N a_N
Q
c_1 y_1 b_1
:
c_Q y_Q b_Q

1 行目には、はじめから並んでいる看板の数を表す整数 N が与えられる。 続く N 行には、はじめから並んでいる看板の位置と色を表す整数 x_i 、a_i が与えられる。 N+2 行目には、看板の追加・削除の回数を表す整数 Q が与えられる。 続く Q 行には、看板の追加・削除を表す整数 c_i 、y_i 、b_i が与えられる。 c_i はクエリの種類を表す。 c_i = 1 のとき看板の追加を意味し、y_i の位置に b_i の色の看板が追加される。 c_i = 2 のとき看板の削除を意味し、y_i の位置にある b_i の色の看板が削除される。

制約

• 1 ≤ N ≤ 100,000
• -10^9 ≤ x_i ≤ 10^9
• 1 ≤ a_i ≤ 200,000
• 1 ≤ Q ≤ 100,000
• 1 ≤ c_i ≤ 2
• -10^9 ≤ y_i ≤ 10^9
• 1 ≤ b_i ≤ 200,000
• 削除のクエリに対して削除される看板は必ず存在する。
• 任意の時点で看板の個数が 0 になることはない。
• 任意の時点で同じ位置に複数の看板が存在することはない。

部分点

この問題には部分点が設定されている。この問題のテストケースのうち 30 点分は追加で以下の制約を満たす。

• 1 ≤ N ≤ 2,000
• 1 ≤ Q ≤ 2,000

出力

各追加と削除が行われた後の看板の列に対して、イクタ君がすべての看板を同じ色に塗り替えるのに必要な最小の時間を 1 行づつ出力せよ。

入力例1

1
10 1
3
1 2 2
1 -2 3
2 10 1

出力例1

3
9
3

1 つめのクエリで看板が追加された時点では、位置 x=2 に色 a=2 の看板が、位置 x=10 に色 a=1 の看板があるので、 x=2 の看板を色 a=1 で塗り替えると時間 3 ですべての看板が同じ色になる。

2 つめのクエリで看板が追加された時点では、位置 x=-2 に色 a=3 の看板が、位置 x=2 に色 a=2 の看板が、位置 x=10 に色 a=1 の看板があるので、 x=-2 の看板を色 a=1 で塗り替えたあと、x=2 の看板を色 a=1 で塗り替えると時間 9 ですべての看板が同じ色になる。

3 つめのクエリで看板が削除された時点では、位置 x=-2 に色 a=3 の看板が、位置 x=2 に色 a=2 の看板があるので、どちらかの看板をもう一方の看板の色に塗り替えると時間 3 ですべての看板が同じ色になる。

問題

背景

ゲーム研究者のビッグブリッジ伯爵は、SOUND VERTEX III - GRAPH WARS というゲームの乱数生成にLFSR (日本語版 Wikipedia) という乱数生成方式が使われていることを発見した。 合法的にチートをする最高のパフォーマンスを発揮するために、乱数生成器の内部状態が特定の値となるタイミングを知りたい。

課題

三つの非負整数A, B, Xが与えられる。 0 以上の任意の整数 t に対して、乱数生成器の時刻 t での内部状態 a_t は次の式で与えられる。

• a_0\ =\ A
• a_{t+1}\ =\ (a_t\ /\ 2)\ \^\ (a_t\ %\ 2\ \times\ B)

ただし、" \times ", "/", "%"はそれぞれ整数での乗算, 除算, 剰余算、"^"は二進数表現でのビットごとのxor演算を表す。

a_t = X となる最小の t を出力せよ。 そのような t が存在しない場合は -1 を出力すること。

配点

300

入力

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

A B X

制約

• 0 ≤ A, B, X < 2^{36}

部分点

この問題には部分点が設定されている。この問題のテストケースのうち 30 点分は追加で以下の制約を満たす。

• 0 ≤ A, B, X < 2^{10}

出力

a_t = X となるような最小の t を一行で出力せよ。

入力例1

7 6 5

出力例1

1

a_0 = 7, a_1 = (7 / 2) \^ 6 = 5 なので t = 1 となる。

入力例2

9 6 1

出力例2

2

a_0 = 9, a_1 = 2, a_2 = 1 である。

入力例3

3 4 6

出力例3

2

入力例4

8 7 6

出力例4

-1

問題

背景

数式検索の研究をしていたビッグブリッジ伯爵はある日、数式のハッシュ値を計算することによって効率よく数式検索をすることが出来るのではないかと考えた。
そこで、ある特定の条件を満たす多項式に対しては、変数に 1 か -1 を割り当ててその多項式を計算した時にその多項式が最小値を取るような変数の割り当ての総数を、その多項式のハッシュとすることにした。

しかし、ビッグブリッジ伯爵は他にも様々なアイディアを実装するので忙しい。
そこであなたは、ビッグブリッジ伯爵の代わりに数式のハッシュ値を計算するプログラムを書くことになった。

課題

30 変数以下の 2 次多項式 P が以下の制約のもとで与えられる。

• 多項式に現れる変数はA-Z, a-dのいずれか
• 多項式は必ず Σ 1 * x_i * x_j という形になっている
  • x_i, x_j はA-Z,a-dのどれかになっている
  • a * A + A * a => 2 * a * A や、 A * A + A * A => 2 * A * A のように整理したときに係数が 1 でない項があるようなものは与えらない
• 全ての変数はたかだか 4 回しか多項式に出現しない

各変数の値が -1, 1 のどちらかしかとらないとき、多項式が最小値を取るような変数の割り当て方の総数を求めよ。

配点

300

入力

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

P

制約

入力 P は 1 文字の変数(A-Zとa-dのどれか)と掛け算を表す *、足し算を表す+のみで構成される。
P の中にA-Z,a-d,*,+以外の文字は出現しない。
課題に書かれている条件を満たす。

部分点

この問題には部分点が設定されている。この問題のテストケースのうち 30 点分は追加で以下の制約を満たす。

• 入力に出現する変数の種類が 20 種類以下

出力

最小値を取るような変数の割り当て方の総数 T を 1 行で出力せよ。

入力例1

a*A

出力例1

2

a=1 , A=-1 あるいは a=-1 , A=1 という 2 通りの割り当てが最小値を取る。

入力例2

a*A+b*b+c*a+b*a+A*b

出力例2

6

入力例3

A*C+A*V+A*W+B*M+B*R+B*c+C*J+C*T+D*M+D*Q+D*b+E*P+E*Y+E*c+F*Q+F*R+F*d+G*H+G*X+G*Y+H*J+H*L+I*K+I*L+I*M+J*Q+K*L+K*Z+N*T+N*Y+N*d+O*S+O*X+O*Z+P*U+P*V+R*U+S*V+S*b+T*d+U*a+W*X+W*b+Z*a+a*c

出力例3

30