题目描述

有 $n$ 个格子，编号为 $0 \sim n-1$。初始时所有格子均为白色。

共进行三次染色，第 $i$ ($1 \le i \le 3$) 次染色会给定 $a_i, b_i$，满足 $0 \le b_i < a_i$，然后按照如下规则染色：

• 对于所有 $0 \le x < n$，若 $x \bmod a_i = b_i$，则将编号为 $x$ 的格子染为黑色。

三次染色后，求有多少不同的区间 $[l, r]$ 满足 $0 \le l \le r < n$ 且编号在 $l \sim r$ 内的格子均为白色。由于答案可能较大，你只需要求出答案对 $998,244,353$ 取模后的结果。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $n$，表示格子的数量。

输入的第 $i+1$ ($1 \le i \le 3$) 行包含两个非负整数 $a_i, b_i$，表示第 $i$ 次染色给定的参数。

输出格式

输出到标准输出。

输出一行一个非负整数表示满足条件的区间数量对 $998,244,353$ 取模后的结果。

10
5 3
7 0
7 1

8

1000000
114514 114
114514 810
200000 5

136032633

提示

【子任务】

对于所有测试数据，均有：

• $1 \le n \le 10^{13}$；
• 对于所有 $1 \le i \le 3$，均有 $0 \le b_i < a_i \le 2n$。

子任务编号	分值	$n \le$	特殊性质
1	5	$10^6$	无
2	25	$10^{13}$	$a_3 > b_3 \ge n$
3	5		$n/a_1, n/a_2 \le 10^5$
4			$n/a_1 \le 10^5$
5	20		$a_1, a_2, a_3 \le 10^3$
6	40		无

【评分方式（洛谷疑似无法支持）】

对于每个子任务：

1. 正确回答所有满足 $a_1, a_2, a_3$ 两两互质的测试数据的答案，可获得该子任务 $60\%$ 的分数；
2. 正确回答所有测试数据的答案，可获得该子任务 $100\%$ 的分数