C - AtCoDeer and Election Report

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

シカのAtCoDeerくんは選挙速報を見ています。選挙には二人の候補高橋くんと青木くんが出ています。速報では、現在の二人の得票数の比が表示されていますが、得票数そのものは表示されていません。AtCoDeerくんは N 回画面を見て、 i(1≦i≦N) 回目に見たときに表示されている比は T_i:A_i でした。ここで、AtCoDeerくんが選挙速報の画面を1回目に見た段階で既にどちらの候補にも少なくとも一票は入っていたことがわかっています。 N 回目に画面を見たときの投票数(二人の得票数の和)として考えられるもののうち最小となるものを求めてください。ただし、得票数が途中で減ることはありません。

### 制約

• 1≦N≦1000
• 1≦T_i,A_i≦1000 (1≦i≦N)
• T_iA_i は互いに素 (1≦i≦N)
• 答えが 10^{18} 以下になることは保証されている

### 入力

N
T_1 A_1
T_2 A_2
:
T_N A_N


### 出力

N 回目に画面を見たときの投票数として考えられる最小値を出力せよ。

### 入力例 1

3
2 3
1 1
3 2


### 出力例 1

10


### 入力例 2

4
1 1
1 1
1 5
1 100


### 出力例 2

101


### 入力例 3

5
3 10
48 17
31 199
231 23
3 2


### 出力例 3

6930


Score : 300 points

### Problem Statement

AtCoDeer the deer is seeing a quick report of election results on TV. Two candidates are standing for the election: Takahashi and Aoki. The report shows the ratio of the current numbers of votes the two candidates have obtained, but not the actual numbers of votes. AtCoDeer has checked the report N times, and when he checked it for the i-th (1≦i≦N) time, the ratio was T_i:A_i. It is known that each candidate had at least one vote when he checked the report for the first time.

Find the minimum possible total number of votes obtained by the two candidates when he checked the report for the N-th time. It can be assumed that the number of votes obtained by each candidate never decreases.

### Constraints

• 1≦N≦1000
• 1≦T_i,A_i≦1000 (1≦i≦N)
• T_i and A_i (1≦i≦N) are coprime.
• It is guaranteed that the correct answer is at most 10^{18}.

### Input

The input is given from Standard Input in the following format:

N
T_1 A_1
T_2 A_2
:
T_N A_N


### Output

Print the minimum possible total number of votes obtained by Takahashi and Aoki when AtCoDeer checked the report for the N-th time.

### Sample Input 1

3
2 3
1 1
3 2


### Sample Output 1

10


When the numbers of votes obtained by the two candidates change as 2,3 → 3,3 → 6,4, the total number of votes at the end is 10, which is the minimum possible number.

### Sample Input 2

4
1 1
1 1
1 5
1 100


### Sample Output 2

101


It is possible that neither candidate obtained a vote between the moment when he checked the report, and the moment when he checked it for the next time.

### Sample Input 3

5
3 10
48 17
31 199
231 23
3 2


### Sample Output 3

6930

D - AtCoDeer and Rock-Paper

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

シカのAtCoDeerくんは友達のTopCoDeerくんとあるゲームをして対戦しています。 このゲームは N ターンからなります。各ターンではそれぞれのプレイヤーはじゃんけんのグーかパーを出します。ただし、各プレイヤーは次の条件を満たす必要があります。

(※) 各ターンの後で、(今までにパーを出した回数)(今までにグーを出した回数)　を満たす

このゲームでの各プレイヤーの得点は、(勝ったターンの数) - (負けたターンの数) です。 AtCoDeerくんは特殊能力を持っているので、ゲームが始まる前にTopCoDeerくんの出す N ターンの手を全て知ることが出来ました。 AtCoDeerくんの各ターンでの手を決めて、AtCoDeerくんの得点を最大化してください。 TopCoDeerくんの出す手の情報は文字列 s で与えられます。 si(1≦i≦N) 文字目が gのときは i ターン目でTopCoDeerくんがグーを出すことを、 pのときはパーを出すことを表します。

### 制約

• 1≦N≦10^5
• N=|s|
• s の各文字はgp
• s で表される手は、条件(※)を満たしている

### 入力

s


### 出力

AtCoDeerくんの得点の最大値を出力せよ。

### 入力例 1

gpg


### 出力例 1

0


### 入力例 2

ggppgggpgg


### 出力例 2

2


Score : 300 points

### Problem Statement

AtCoDeer the deer and his friend TopCoDeer is playing a game. The game consists of N turns. In each turn, each player plays one of the two gestures, Rock and Paper, as in Rock-paper-scissors, under the following condition:

(※) After each turn, (the number of times the player has played Paper)(the number of times the player has played Rock).

Each player's score is calculated by (the number of turns where the player wins) - (the number of turns where the player loses), where the outcome of each turn is determined by the rules of Rock-paper-scissors.

(For those who are not familiar with Rock-paper-scissors: If one player plays Rock and the other plays Paper, the latter player will win and the former player will lose. If both players play the same gesture, the round is a tie and neither player will win nor lose.)

With his supernatural power, AtCoDeer was able to foresee the gesture that TopCoDeer will play in each of the N turns, before the game starts. Plan AtCoDeer's gesture in each turn to maximize AtCoDeer's score.

The gesture that TopCoDeer will play in each turn is given by a string s. If the i-th (1≦i≦N) character in s is g, TopCoDeer will play Rock in the i-th turn. Similarly, if the i-th (1≦i≦N) character of s in p, TopCoDeer will play Paper in the i-th turn.

### Constraints

• 1≦N≦10^5
• N=|s|
• Each character in s is g or p.
• The gestures represented by s satisfy the condition (※).

### Input

The input is given from Standard Input in the following format:

s


### Output

Print the AtCoDeer's maximum possible score.

### Sample Input 1

gpg


### Sample Output 1

0


Playing the same gesture as the opponent in each turn results in the score of 0, which is the maximum possible score.

### Sample Input 2

ggppgggpgg


### Sample Output 2

2


For example, consider playing gestures in the following order: Rock, Paper, Rock, Paper, Rock, Rock, Paper, Paper, Rock, Paper. This strategy earns three victories and suffers one defeat, resulting in the score of 2, which is the maximum possible score.

E - Building Cubes with AtCoDeer

Time Limit: 4 sec / Memory Limit: 256 MB

### 問題文

シカのAtCoDeerくんは正方形のタイルを N 枚持っています。 各正方形の片面には 1～N の数が書いてあって、正方形の各頂点にはそれぞれ色が塗られています。色は 0～999の整数で表され、 i と書かれた正方形に塗られている色は、数の書かれている方向から見て左上、右上、右下、左下 の順に、 C_{i,0},C_{i,1},C_{i,2},C_{i,3} で与えられます(図1を参照)。

1: タイルの色と入力の対応

AtCoDeerくんはこれらのタイルを6枚組み合わせて次のような条件を満たす立方体を作ろうと考えました。

• 数の書いてある面が外側を向いている
• 立方体の各頂点に対し、そこに集まる正方形の頂点は3つあるが、それらには全て同じ色が塗られている

AtCoDeerくんのために条件を満たす立方体が何通りあるか求めてください。ただし、正方形には数が書いてあるので、色の構成が同じだとしても使ったタイルが異なったり、使ったタイルの向き(90°回転により4通り考えられる)が異なるものは異なる立方体とみなします。 ただし、3次元空間で回転させることで使ったタイルの向きまで完全に一致するものは同じ立方体とみなします。

2: 4方向のタイルの向き

### 制約

• 6≦N≦400
• 0≦C_{i,j}≦999 (1≦i≦N , 0≦j≦3)

### 入力

N
C_{1,0} C_{1,1} C_{1,2} C_{1,3}
C_{2,0} C_{2,1} C_{2,2} C_{2,3}
:
C_{N,0} C_{N,1} C_{N,2} C_{N,3}


### 出力

AtCoDeerくんが作れる立方体が何通りあるか出力せよ。

### 入力例 1

6
0 1 2 3
0 4 6 1
1 6 7 2
2 7 5 3
6 4 5 7
4 0 3 5


### 出力例 1

1


### 入力例 2

8
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1


### 出力例 2

144


### 入力例 3

6
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0


### 出力例 3

122880


Score : 900 points

### Problem Statement

AtCoDeer the deer has N square tiles. The tiles are numbered 1 through N, and the number given to each tile is written on one side of the tile. Also, each corner of each tile is painted in one of the 1000 colors, which are represented by the integers 0 between 999. The top-left, top-right, bottom-right and bottom-left corner of the tile with the number i are painted in color C_{i,0}, C_{i,1}, C_{i,2} and C_{i,3}, respectively, when seen in the direction of the number written on the tile (See Figure 1).

Figure 1: The correspondence between the colors of a tile and the input

AtCoDeer is constructing a cube using six of these tiles, under the following conditions:

• For each tile, the side with the number must face outward.
• For each vertex of the cube, the three corners of the tiles that forms it must all be painted in the same color.

Help him by finding the number of the different cubes that can be constructed under the conditions. Since each tile has a number written on it, two cubes are considered different if the set of the used tiles are different, or the tiles are used in different directions, even if the formation of the colors are the same. (Each tile can be used in one of the four directions, obtained by 90° rotations.) Two cubes are considered the same only if rotating one in the three dimensional space can obtain an exact copy of the other, including the directions of the tiles.

Figure 2: The four directions of a tile

### Constraints

• 6≦N≦400
• 0≦C_{i,j}≦999 (1≦i≦N , 0≦j≦3)

### Input

The input is given from Standard Input in the following format:

N
C_{1,0} C_{1,1} C_{1,2} C_{1,3}
C_{2,0} C_{2,1} C_{2,2} C_{2,3}
:
C_{N,0} C_{N,1} C_{N,2} C_{N,3}


### Output

Print the number of the different cubes that can be constructed under the conditions.

### Sample Input 1

6
0 1 2 3
0 4 6 1
1 6 7 2
2 7 5 3
6 4 5 7
4 0 3 5


### Sample Output 1

1


The cube below can be constructed.

### Sample Input 2

8
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1


### Sample Output 2

144


### Sample Input 3

6
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0


### Sample Output 3

122880

F - Painting Graphs with AtCoDeer

Time Limit: 2 sec / Memory Limit: 512 MB

### 問題文

シカのAtCoDeerくんはある日、 N 頂点 M 辺からなる単純な(すなわち、多重辺と自己ループのない)グラフを拾いました。頂点には1,2,..,Nの番号がついていて互いに区別が可能で、辺は(a_i,b_i) (1≦i≦M)で表されます。 AtCoDeerくんは K 色のペンキを使って各辺を塗ろうとしています。ペンキは大量にあるので同じ色で複数の辺を塗ることが可能です。 AtCoDeerくんの拾ったグラフは特殊な形状をしているため、単純なサイクル(すなわち,サイクルであって同じ頂点を一度しか通らないもの)を選んで、そのサイクル上の辺の色をひとつずつサイクルに沿ってずらすことが出来ます。正確に言うと、サイクル上の辺を順に e_1, e_2,..,e_a とすると、 e_1 に塗られていた色を e_2 に、e_2 に塗られていた色を e_3 に、 ...e_{a-1} に塗られていた色を e_a に、e_a に塗られていた色を e_1 に、同時に塗り替えることが出来ます。

1: 操作の例

### 制約

• 1≦N≦50
• 1≦M≦100
• 1≦K≦100
• 1≦a_i,b_i≦N (1≦i≦M)
• グラフには自己ループや多重辺はない。

### 入力

N M K
a_1 b_1
a_2 b_2
:
a_M b_M


### 入力例 1

4 4 2
1 2
2 3
3 1
3 4


### 出力例 1

8


### 入力例 2

5 2 3
1 2
4 5


### 出力例 2

9


### 入力例 3

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


### 出力例 3

569519295


Score : 1300 points

### Problem Statement

One day, AtCoDeer the deer found a simple graph (that is, a graph without self-loops and multiple edges) with N vertices and M edges, and brought it home. The vertices are numbered 1 through N and mutually distinguishable, and the edges are represented by (a_i,b_i) (1≦i≦M).

He is painting each edge in the graph in one of the K colors of his paint cans. As he has enough supply of paint, the same color can be used to paint more than one edge.

The graph is made of a special material, and has a strange property. He can choose a simple cycle (that is, a cycle with no repeated vertex), and perform a circular shift of the colors along the chosen cycle. More formally, let e_1, e_2, ..., e_a be the edges along a cycle in order, then he can perform the following simultaneously: paint e_2 in the current color of e_1, paint e_3 in the current color of e_2, ..., paint e_a in the current color of e_{a-1}, and paint e_1 in the current color of e_{a}.

Figure 1: An example of a circular shift

Two ways to paint the edges, A and B, are considered the same if A can be transformed into B by performing a finite number of circular shifts. Find the number of ways to paint the edges. Since this number can be extremely large, print the answer modulo 10^9+7.

### Constraints

• 1≦N≦50
• 1≦M≦100
• 1≦K≦100
• 1≦a_i,b_i≦N (1≦i≦M)
• The graph has neither self-loops nor multiple edges.

### Input

The input is given from Standard Input in the following format:

N M K
a_1 b_1
a_2 b_2
:
a_M b_M


### Output

Print the number of ways to paint the edges, modulo 10^9+7.

### Sample Input 1

4 4 2
1 2
2 3
3 1
3 4


### Sample Output 1

8


### Sample Input 2

5 2 3
1 2
4 5


### Sample Output 2

9


### Sample Input 3

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


### Sample Output 3

569519295