There are $n$ cells, numbered $0 \sim n-1$. Initially, all cells are white.
Three coloring operations are performed. For each $i$ ($1 \le i \le 3$), $a_i$ and $b_i$ are given, satisfying $0 \le b_i < a_i$. The coloring rule is as follows: * For all $0 \le x < n$, if $x \pmod{a_i} = b_i$, then the cell numbered $x$ is colored black.
After the three coloring operations, find the number of distinct intervals $[l, r]$ such that $0 \le l \le r < n$ and all cells numbered $l \sim r$ are white. Since the answer may be large, you only need to output the result modulo $998,244,353$.
Input
Read data from standard input. The first line contains a positive integer $n$, representing the number of cells. The $(i+1)$-th line ($1 \le i \le 3$) contains two non-negative integers $a_i$ and $b_i$, representing the parameters given for the $i$-th coloring operation.
Output
Output to standard output. Output a single line containing a non-negative integer representing the number of intervals satisfying the condition, modulo $998,244,353$.
Examples
Input 1
10 5 3 7 0 7 1
Output 1
8
Input 2
1000000 114514 114 114514 810 200000 5
Output 2
136032633
Constraints
For all test data: $1 \le n \le 10^{13}$; For all $1 \le i \le 3$, $0 \le b_i < a_i \le 2n$.
| Subtask ID | Score | $n \le$ | Special Property |
|---|---|---|---|
| 1 | 5 | $10^6$ | None |
| 2 | 25 | $10^{13}$ | $a_3 > b_3 \ge n$ |
| 3 | 5 | $10^{13}$ | $n/a_1, n/a_2 \le 10^5$ |
| 4 | 5 | $10^{13}$ | $n/a_1 \le 10^5$ |
| 5 | 20 | $10^{13}$ | $a_1, a_2, a_3 \le 10^3$ |
| 6 | 40 | $10^{13}$ | None |
Note
For each subtask: 1. Correctly answering all test cases where $a_1, a_2, a_3$ are pairwise coprime earns 60% of the subtask's score. 2. Correctly answering all test cases earns 100% of the subtask's score.