시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

Your favorite singer is giving a farewell concert soon, and you just can't miss this.

The concert will be held in a hall which has $n$ rows, numbered from 0 to $n - 1$, with $m$ seats in each row, consecutively numbered from 0 to $m - 1$.

Unfortunately, $k$ seats are already unavailable for reservation. These seats are given by pairs $(r_1, s_1)$, $(r_2, s_2)$, $...$, $(r_k, s_k)$. For every $i$ from 1 to $k$, the ticket for seat $s_i$ in row $r_i$ is gone.

You are definitely coming to the concert, but you have no idea if any of your friends would like to join. You are considering all options to buy tickets for several (at least one) consecutive seats in the same row. How many such options do you have?

입력

The first line of the input contains three integers $n$, $m$ and $k$ ($1 \le n, m \le 10^5$; $1 \le k \le n \cdot m$) --- the dimensions of the concert hall and the number of reserved seats, respectively.

The second line of the input contains three integers $r_1$, $a_r$ and $b_r$ ($0 \le r_1, a_r, b_r < n$).

The third line of the input contains three integers $s_1$, $a_s$ and $b_s$ ($0 \le s_1, a_s, b_s < m$).

As the input could be quite large, it's encoded in the following way: the values of $r_1$ and $s_1$ are given, and for every $i$ from 2 to $k$ the values of $r_i$ and $s_i$ can be found using the following formulae:

$r_i = (r_{i-1} \cdot a_r + b_r) \bmod n$;

$s_i = (s_{i-1} \cdot a_s + b_s) \bmod m$.

All pairs $(r_i, s_i)$ are distinct.

출력

Output a single integer --- the number of options to buy tickets for several consecutive seats in the same row.

예제 입력 1

3 4 3
1 2 0
2 1 1

예제 출력 1

18

예제 입력 2

22 13 41
7 12 14
5 8 1

예제 출력 2

1195

힌트

In the first example test case, seats $(1, 2)$, $(2, 0)$ and $(1, 1)$ are occupied. There are 10 options to buy tickets in row 0, 2 options in row 1 and 6 options in row 2. The sum is $10 + 2 + 6 = 18$.