题目描述

有 $3$ 台信号灯，编号为 $1,\ 2,\ 3$。信号灯 $i$ 的工作模式为：“绿灯持续 $g_i$ 秒，红灯持续 $r_i$ 秒，绿灯持续 $g_i$ 秒，红灯持续 $r_i$ 秒，……”，如此无限循环。

现在，$3$ 台信号灯同时变为绿灯。在接下来的 $(g_1 + r_1)(g_2 + r_2)(g_3 + r_3)$ 秒内，所有信号灯同时为绿灯的总时间是多少秒？请将答案对 $119\times 2^{23}+1$ 取模后输出。

输入格式

输入从标准输入读入，格式如下：

$g_1$ $r_1$ $g_2$ $r_2$ $g_3$ $r_3$

输出格式

输出答案。

样例 1

输入

1 1 2 1 3 1

输出

8

样例 2

输入

7 3 5 7 11 4

输出

420

样例 3

输入

999999999991 999999999992 999999999993 999999999994 999999999995 999999999996

输出

120938286

说明/提示

限制

• $1 \leq g_1, r_1, g_2, r_2, g_3, r_3 \leq 10^{12}$
• 输入中的所有值均为整数。

样例解释 1

在接下来的 $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$ 秒。

由 ChatGPT 4.1 翻译