問題文

縦 H マス、横 W マスの白いマス目があります。高橋君は、上下または左右に隣り合う 2 マスを選び、それら 2 マスを黒く塗ります。高橋君が 2 マスを黒く塗る方法は何通りか求めてください。

制約

• 1≦H，W≦100

入力例1

2 3

出力例1

7

図の 7 通りです。

入力例2

4 1

出力例2

3

図の 3 通りです。

入力例3

1 1

出力例3

0

問題文

高橋君は文字列 S を持っています。S は英小文字のみからなります。

まず、高橋君は S の文字を任意の順番に並べ替え、文字列 S' を作ります。

次に、高橋君は S' を任意の位置で分割し、何個かの文字列 s_1，s_2，...，s_N を作ります（N は任意）。ただし、各 s_i は回文でなければなりません。

各 s_i の長さの最小値を X とします。高橋君は X をできるだけ大きくしようとしています。X の最大値を求めてください。

制約

• 1≦|S|≦10^5
• S は英小文字のみからなる。

入力例1

rokovoko

出力例1

3

例えば、krk，oovoo とすればよいです。

入力例2

tomtom

出力例2

6

例えば、mottom とすればよいです。

入力例3

vwxyz

出力例3

1

例えば、v，w，x，y，z とすればよいです。

入力例4

succeeded

出力例4

3

問題文

高橋君は N 個の魔法を覚えています。魔法は 1 から N まで番号が振られています。

最初、気温は 0 度です。高橋君が i 番目の魔法を唱えると、気温が a_i 度だけ上がった後 b_i 度だけ下がります。

高橋君はすべての魔法をちょうど 1 回ずつ唱えます。この間の気温の最大値を X 度とします。高橋君は魔法を唱える順番を工夫して、X をできるだけ小さくしようとしています。X の最小値を求めてください。

制約

• 1≦N≦10^5
• a_i，b_i は整数である。
• 1≦a_i，b_i≦10^9

入力例1

1
10 20

出力例1

10

唯一の魔法を唱えると、気温は 0 → 10 → -10 度と変化します。

入力例2

2
30 20
10 20

出力例2

20

2 番目の魔法、1 番目の魔法の順に唱えると、気温は 0 → 10 → -10 → 20 → 0 度と変化します。

入力例3

5
5 10
10 5
10 15
15 10
20 20

出力例3

10

例えば、1，3，5，2，4 番目の魔法の順に唱えればよいです。

問題文

それぞれ N 枚のカードからなる山が 2 つあります。これらを山 A, B とします。

山 A の上から i 番目のカードには、整数 a_i が書かれています。ただし、(a_1，...，a_N) は 1 から N までの順列です。

山 B の上から i 番目のカードには、整数 b_i が書かれています。ただし、(b_1，...，b_N) は 1 から N までの順列です。

高橋君は次の一連の操作を 2N-2 回行い、長さ 2N-2 の数列を作ります。

• 山 A, B のうちカードが 2 枚以上残っている方を好きに選ぶ。
• 選んだ方の山の一番上のカードを取り除く。
• 選ばなかった方の山の一番上のカードに書かれた数を、数列の末尾に追加する。

高橋君が作ることのできる数列は何通りか、10^9+7 で割った余りを求めてください。

制約

• 2≦N≦1,000
• (a_1，...，a_N) は 1 から N までの順列である。
• (b_1，...，b_N) は 1 から N までの順列である。

入力例1

2
1 2
2 1

出力例1

2

山 A，B の順に選ぶと数列 (2，2) が得られ、山 B，A の順に選ぶと数列 (1，1) が得られます。

入力例2

3
1 2 3
2 3 1

出力例2

5

次の 5 通りの数列を作ることができます。

• (1，1，1，1)
• (1，3，2，1)
• (1，3，3，3)
• (2，2，2，1)
• (2，2，3，3)

入力例3

5
3 1 4 2 5
3 2 4 1 5

出力例3

58