問題文

あなたはあるコンテストのために問題を 3 問作りました。 検討の結果、これらの問題の配点は以下のようにすることになりました。

• 1 問目の配点は A 点または A + 1 点にする。
• 2 問目の配点は B 点または B + 1 点にする。
• 3 問目の配点は C 点または C + 1 点にする。

3 問の配点の合計をちょうど S 点にすることができるかどうか判定してください。

制約

• 1 \leq A, B, C \leq 20
• 1 \leq S \leq 60
• 入力値はすべて整数である。

入力例 1

3
5
10
20

出力例 1

Yes

たとえば、1, 2, 3 問目の配点をそれぞれ 3, 6, 11 点にすることで、配点の合計を S = 20 点にすることができます。

入力例 2

10
8
15
30

出力例 2

No

入力例 3

1
3
5
50

出力例 3

No

問題文

みかんが N 個あり、1, 2, ..., N の番号がついています。 それぞれのみかんにはちょうど A 個またはちょうど B 個の房があります。

これらのみかんの房の個数について、以下のことがわかっています。

• 各 i (1 \leq i \leq M) について、番号が L_i 以上 R_i 以下のみかんには房がそれぞれちょうど A 個ある。

N 個のみかんの房の個数の合計として考えられる値のうち最大のものを求めてください。

制約

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• 1 \leq A < B \leq 100
• 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
• 入力値はすべて整数である。

入力例 1

5 2 6 7
2 3
3 4

出力例 1

32

それぞれのみかんの房の個数が以下のようになっているとき、房の個数の合計が最大となります。

• みかん 2, 3, 4 には房がそれぞれ A = 6 個ある。
• みかん 1, 5 には房がそれぞれ B = 7 個ある。

このときの房の個数の合計は 6 \times 3 + 7 \times 2 = 32 となります。

入力例 2

10 3 20 30
1 6
2 7
3 10

出力例 2

200

すべてのみかんが A = 20 個の房を持ちます。

入力例 3

100 5 12 34
6 8
81 81
26 26
90 91
49 50

出力例 3

3202

問題文

長さ N の整数列 A_1, A_2, ..., A_N が与えられます。 この数列に以下の操作をちょうど K 回施します。

• 添字 i (1 \leq i \leq N) を一つ選ぶ。A_i を 2 で割る。ただし商は整数単位で計算し、あまりは切り捨てる。

K 回の操作のあとの数列としてありうるものの個数を 10^9 + 7 で割ったあまりを求めてください。

制約

• 1 \leq N \leq 50
• 0 \leq A_i \leq 10^{18} (1 \leq i \leq N)
• 0 \leq K \leq 10^9
• 入力値はすべて整数である。

入力例 1

3 2
0 3 4

出力例 1

6

はじめ、数列 A は A = [0, 3, 4] です。 K = 2 回の操作のあとの数列としてありうるものとしては、[0, 3, 4] や [0, 1, 2] などがあります。

数列 [0, 3, 4] は以下のようにして実現できます。

• i = 1 を選ぶ。数列は [0, 3, 4] となる。
• i = 1 を選ぶ。数列は [0, 3, 4] となる。

また、数列 [0, 1, 2] はたとえば以下のようにして実現できます。

• i = 2 を選ぶ。数列は [0, 1, 4] となる。
• i = 3 を選ぶ。数列は [0, 1, 2] となる。

入力例 2

3 100
1 1 1

出力例 2

7

入力例 3

5 7
10 12 15 20 30

出力例 3

330

入力例 4

7 1000000000
100261694256177806 55017793609323647 50568971510512136 98912633370372323 51937770757669401 50688484559490819 108712166294779912

出力例 4

322647718

問題文

高橋くんの家は x 軸上の点 0 に、AtCoder 社のオフィスは x 軸上の点 D にあります。 また、x 軸上には N 個のガソリンスタンドがあり、これらの座標は X_1, X_2, ..., X_N です。

高橋くんは毎日家からオフィスまで自動車で移動します。 この自動車の燃料タンクの容量は F リットルであり、距離 1 移動するごとに燃料を 1 リットル消費します。 高橋くんは燃料タンクが満タンの状態で家を出発し、ガソリンスタンドを通るごとに以下のようにして自動車の燃料を補給します。

• 燃料が T リットル以上残っている場合、燃料を補給しない。
• そうでない場合、燃料タンクが満タンになるまで燃料を補給する。

オフィスへの移動の際、自動車は x 軸正方向にしか進むことができません。ガソリンスタンドでもオフィスでもない場所で燃料タンクが空になった場合、オフィスへの移動は失敗となります。

あなたは N 個のガソリンスタンドのうちのいくつか (0 個でも構いません) を書店に建て替えようとしています。 書店に建て替えるガソリンスタンドの集合であって、建て替えのあとも高橋くんが上記の方法で家からオフィスまで自動車で移動できるようなものの個数を 10^9 + 7 で割ったあまりを求めてください。

制約

• 0 < T \leq F \leq 10^9
• 1 \leq N \leq 100,000
• 0 < X_1 < X_2 < ... < X_N < D \leq 10^9
• 入力値はすべて整数である。

入力例 1

10 8 5 2
3 7

出力例 1

2

座標 X_1 = 3, X_2 = 7 のガソリンスタンドにそれぞれ 1, 2 の番号をつけたとき、条件を満たす集合は \{\}, \{1\} の 2 個となります。

入力例 2

8 8 5 5
1 2 3 4 5

出力例 2

32

入力例 3

100 50 30 1
40

出力例 3

0

入力例 4

1000 752 687 10
94 186 299 395 406 430 772 782 807 999

出力例 4

1002

問題文

オレンジが X 個、みかんが Y 個あります。 また、人が N 人おり、N は X + Y の約数となっています。 これら X + Y 個の果物を、各人がちょうど (X + Y) / N 個の果物を受け取るように、これら N 人で分けることにしました。

i 人目の人はオレンジ 1 個あたり A_i、みかん 1 個あたり B_i の満足度を得ます。 すなわち、i 人目の人がオレンジを x 個、みかんを y 個受け取った場合、この人が得る満足度は A_i x + B_i y となります。

最も大きい満足度を得る人の満足度と最も小さい満足度を得る人の満足度の差をできるだけ小さくするように果物の分け方を選んだときの、この差を求めてください。

制約

• 0 \leq X \leq 10^5
• 0 \leq Y \leq 10^5
• X + Y \geq 1
• N \geq 2
• N は X + Y の正の約数である。
• 1 \leq A_i, B_i \leq 10^9 (1 \leq i \leq N)
• 入力値はすべて整数である。

入力例 1

4 5 3
10 5
8 7
4 11

出力例 1

3

たとえば以下のように果物を分けることで最小値を達成できます。

• 1 人目はオレンジを 1 個、みかんを 2 個受け取る。20 の満足度を得る。
• 2 人目はオレンジを 1 個、みかんを 2 個受け取る。22 の満足度を得る。
• 3 人目はオレンジを 2 個、みかんを 1 個受け取る。19 の満足度を得る。

入力例 2

3 5 2
1 1
1000000000 1000000000

出力例 2

3999999996

入力例 3

30 60 3
1 100
10 1
100 1

出力例 3

0

入力例 4

1000 1000 5
41 60
78 10
19 100
100 40
30 40

出力例 4

1430