問題文

今、高橋君は長方形の大きな紙を 1 枚と、小さな紙を 2 枚持っています。大きな紙は、縦の長さが H 、横の長さが W です。 2 枚ある小さな紙は、いずれも同じ大きさであり、それぞれ縦の長さが A 、横の長さが B です。

今から高橋君は、 2 枚の小さな紙を大きな紙とそれぞれの辺が平行になるように、縦横の向きを変えずに貼ろうとしています (大きな紙のそれぞれの辺からの距離が整数でない場所に貼ることもできます)。

高橋君は、左上の点が [0,H-A]\times [0,W-B] 上の独立な一様分布に従うようにそれぞれの紙を貼ることにしました。 すでに小さな紙が貼られた上にさらに貼ることも可能です。 小さな紙が 2 枚とも貼られた部分の面積の期待値を計算してください。

制約

• 1 ≤ A < H ≤ 100
• 1 ≤ B < W ≤ 100
• 入力は全て整数

入力例 1

2 2 1 1

出力例 1

0.444444444444

入力例 2

100 99 99 1

出力例 2

1.003378222037

問題文

高橋君は盆栽を 2 つ購入し、一箇所をつないで接ぎ木をしようとしています。

それぞれの盆栽は、 N 頂点の木 A と、M 頂点の木 B として表すことができます。木 A の辺は、頂点 p_{A_i} と頂点 q_{A_i} (1 ≤ i ≤ N-1) を結んでいます。 木 B の辺は、頂点 p_{B_i} と頂点 q_{B_i} (1 ≤ i ≤ M-1) を結んでいます (ただし、木 A の頂点 i と木 B の頂点 i は別の頂点であることに気をつけて下さい)。

木 A の頂点 1 つと木 B の頂点 1 つを辺で結ぶことにより、 1 つの N+M 頂点の木を作ることを考えます。 頂点の選び方は合計で NM 通りあります。この NM 通りそれぞれの木について直径 (2 点間にある辺の本数の最大値) を計算し、その合計を求めてください。

制約

• 2 ≤ N, M ≤ 10^5
• 1 ≤ p_{A_i}, q_{A_i} ≤ N (1 ≤ i ≤ N-1)
• 1 ≤ p_{B_i}, q_{B_i} ≤ M (1 ≤ i ≤ M-1)
• 与えられる 2 つのグラフはそれぞれ木
• 入力は全て整数

入力例 1

4
1 2
2 3
3 4
2
1 2

出力例 1

36

例えば、 A の頂点 2 と B の頂点 1 を新たに辺で結び、N+M 頂点の木を作ると、直径は 4 となります。

入力例 2

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

出力例 2

67

問題文

10^9 \times 10^9 のグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と表すことにします。グリッドのそれぞれのマスは白か黒のどちらかの色になります。最初は全てのマスの色は白です。

今から高橋君は、合計 N 個のスタンプを押します。i 回目 (1 ≤ i ≤ N) は、縦 H_i マス、横 W_i マスの長方形のスタンプを、 左上が (R_i, C_i) と重なるように押します (スタンプの押される部分がグリッドからはみ出すことはありません)。このスタンプは、全体が白いグリッドに押したときに市松模様ができるように設計されており、スタンプの上から p 行目、左から q 列目 (1 ≤ p ≤ H_i, 1 ≤ q ≤ W_i) が押されたマスは、 p+q が偶数ならば白と黒が反転し、奇数ならば変化しません。

N 個のスタンプを押した後、グリッドに黒いマスがいくつあるかを求めてください。

制約

• 1 ≤ N ≤ 10^5
• 1 ≤ H_i ≤ 10^9
• 1 ≤ W_i ≤ 10^9
• 1 ≤ R_i ≤ 10^9
• 1 ≤ C_i ≤ 10^9
• H_i + R_i - 1 ≤ 10^9
• W_i + C_i - 1 ≤ 10^9
• 入力は全て整数

入力例 1

3
3 3 1 1
2 3 2 1
1 2 3 1

出力例 1

7

下の画像はグリッドの左上 3 \times 3 マスの変化を表しています。

入力例 2

5
66518928 212072708 158598694 334005903
54102801 860639145 839206374 16401163
226949335 660240556 476286324 65656871
153262413 54385827 719562883 5920096
496820604 90893558 460217283 428740659

出力例 2

130526013386872287

問題文

N 個の石が左から右に一列に並んでいます。最初、それぞれの石の上には何も障害物が置かれていないので、自由に乗ることができます。

Q 個のクエリを処理してください。クエリには 2 種類あり、入力形式とクエリの内容は以下のとおりです。

• 1 p: 左から p_i 番目の石の上に障害物が置かれていなければ障害物を置き、置かれていれば障害物を取り除く。障害物が置かれた石の上には、乗ることができない。
• 2 l r: 左から l 番目の石の上からスタートし、「1 つ右の石にジャンプする」「2 つ右の石にジャンプする」という操作を繰り返して、障害物が置かれた石の上に一度も乗らずに左から r 番目の石の上にたどり着く方法の総数を 10^9+7 で割った余りを求め、出力する。ただし、左から l 番目や r 番目の石の上に障害物が置かれているときは、0 通りとする。

制約

• 2 ≤ N ≤ 10^9
• 1 ≤ Q ≤ 10^5
• 1 ≤ p ≤ N
• 1 ≤ l < r ≤ N
• 入力は全て整数

入力例 1

7 3
2 4 7
1 3
2 1 7

出力例 1

3
3

最初のクエリでは、次のような移動の仕方があります。

• 1 つ右にジャンプし、1 つ右にジャンプし、1 つ右にジャンプする。
• 1 つ右にジャンプし、2 つ右にジャンプする。
• 2 つ右にジャンプし、1 つ右にジャンプする。

3 個目のクエリでは、次のような移動の仕方があります。

• 1 つ右にジャンプし、2 つ右にジャンプし、1 つ右にジャンプし、1 つ右にジャンプし、1 つ右にジャンプする。
• 1 つ右にジャンプし、2 つ右にジャンプし、1 つ右にジャンプし、2 つ右にジャンプする。
• 1 つ右にジャンプし、2 つ右にジャンプし、2 つ右にジャンプし、1 つ右にジャンプする。

入力例 2

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

出力例 2

8
0
1
0
1
0
0

問題文

N 個の M 階建てビルがあります。 忍者の高橋君は、全てのビルの全ての階に侵入することにしました。 最初、高橋君は 1 番目のビルの 1 階にいて、最終的に再び 1 番目のビルの 1 階に戻ってきたいです。

高橋君は以下の 2 種類の移動ができます。

• 同じビルの隣接する階に階段で移動する。
• 異なるビルの同じ階に瞬間移動する。

ビルに滞在する時間が長くなると見つかる恐れがあるので、途中で同じビルの同じ階に 2 回以上入ることなく、 1 番目のビルの 1 階に戻ってきたいです。

移動の仕方が何通りあるか、 10^9+7 で割った余りを求めてください。

制約

• 2 ≤ N ≤ 100
• 2 ≤ M ≤ 10^9
• 入力は全て整数

入力例 1

3 2

出力例 1

6

次の 6 通りがあります。 (i,j) は i 番目のビルの j 階を表します。

• (1,1) → (2,1) → (3,1) → (3,2) → (2,2) → (1,2) → (1,1)
• (1,1) → (3,1) → (2,1) → (2,2) → (3,2) → (1,2) → (1,1)
• (1,1) → (3,1) → (3,2) → (1,2) → (2,2) → (2,1) → (1,1)
• (1,1) → (1,2) → (2,2) → (3,2) → (3,1) → (2,1) → (1,1)
• (1,1) → (1,2) → (3,2) → (2,2) → (2,1) → (3,1) → (1,1)
• (1,1) → (2,1) → (2,2) → (1,2) → (3,2) → (3,1) → (1,1)

入力例 2

98 7654321

出力例 2

257361229