E - Three Traffic Lights Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1800 点

問題文

3 機の信号機があり、1, 2, 3 と番号が振られています。 信号機 i は、「g_i 秒間青、r_i 秒間赤、g_i 秒間青、r_i 秒間赤、\ldots」というパターンを永久に繰り返します。

いま、3 機の信号機が一斉に青に変わりました。 続く (g_1 + r_1)(g_2 + r_2)(g_3 + r_3) 秒間のうち、全ての信号機が青く点灯している時間帯は合計で何秒あるでしょうか。 この答えを 998,244,353 で割った余りを計算してください。

制約

  • 1 \leq g_1, r_1, g_2, r_2, g_3, r_3 \leq 10^{12}
  • 入力中の全ての値は整数である。

入力

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

g_1 r_1 g_2 r_2 g_3 r_3

出力

答えを出力せよ。

入力例 1

1 1 2 1 3 1

出力例 1

8

続く 24 秒間のうち、

  • 信号機 1 が青く点灯している時間帯は [0, 1], [2, 3], [4, 5], [6, 7], [8, 9], [10, 11], [12, 13], [14, 15], [16, 17], [18, 19], [20, 21], [22, 23] です。
  • 信号機 2 が青く点灯している時間帯は [0, 2], [3, 5], [6, 8], [9, 11], [12, 14], [15, 17], [18, 20], [21, 23] です。
  • 信号機 3 が青く点灯している時間帯は [0, 3], [4, 7], [8, 11], [12, 15], [16, 19], [20, 23] です。

よって、全ての信号機が青く点灯している時間帯は [0, 1], [4, 5], [6, 7], [10, 11], [12, 13], [16, 17], [18, 19], [22, 23] であり、合計で 8 秒あります。

入力例 2

7 3 5 7 11 4

出力例 2

420

入力例 3

999999999991 999999999992 999999999993 999999999994 999999999995 999999999996

出力例 3

120938286

Score : 1800 points

Problem Statement

There are three traffic lights numbered 1, 2, 3. Traffic Light i eternally repeats the following pattern: green for g_i seconds, red for r_i seconds, green for g_i seconds, red for r_i seconds, and so on.

All three lights have turned green just now. During the next (g_1 + r_1)(g_2 + r_2)(g_3 + r_3) seconds, what is the total duration of the time when all lights are green? Compute the answer modulo 998,244,353.

Constraints

  • 1 \leq g_1, r_1, g_2, r_2, g_3, r_3 \leq 10^{12}
  • All values in the input are integers.

Input

Input is given from Standard Input in the following format:

g_1 r_1 g_2 r_2 g_3 r_3

Output

Print the answer.

Sample Input 1

1 1 2 1 3 1

Sample Output 1

8

During the next 24 seconds,

  • Light 1 is green during time intervals [0, 1], [2, 3], [4, 5], [6, 7], [8, 9], [10, 11], [12, 13], [14, 15], [16, 17], [18, 19], [20, 21], [22, 23].
  • Light 2 is green during time intervals [0, 2], [3, 5], [6, 8], [9, 11], [12, 14], [15, 17], [18, 20], [21, 23].
  • Light 3 is green during time intervals [0, 3], [4, 7], [8, 11], [12, 15], [16, 19], [20, 23].

Thus, all lights are green during time intervals [0, 1], [4, 5], [6, 7], [10, 11], [12, 13], [16, 17], [18, 19], [22, 23].

The total duration is 8 seconds.

Sample Input 2

7 3 5 7 11 4

Sample Output 2

420

Sample Input 3

999999999991 999999999992 999999999993 999999999994 999999999995 999999999996

Sample Output 3

120938286