After attending a biology class, Cidoai had a sudden inspiration and came up with this problem.
"Too easy... right?" Cidoai said, handing you this problem so you can discover the joy in it.
One day, at hour $0$, a cell is generated. Every $a$ hours, the number of cells doubles. Every $b$ hours, the number of cells becomes half of the current amount (rounded up).
If the current time is a common multiple of $a$ and $b$, the number of cells remains unchanged. Given $k$ hours have passed, what is the number of cells? Output the answer modulo $998244353$.
Input
A single line containing three positive integers $a, b, k$.
Output
A single integer representing the answer.
Examples
Input 1
3 4 6
Output 1
2
Input 2
4 7 16
Output 2
4
Input 3
3 2 5
Output 3
1
Input 4
114 5141 919810
Output 4
62166352
Note
The number of cells from hour $1$ to $6$ is $1, 1, 2, 1, 1, 2$ respectively.
Constraints
For all data, $1 \le a, b, k \le 10^6$.
This problem uses bundled testing.
| Subtask ID | Score | $k \le$ | Special Properties |
|---|---|---|---|
| $1$ | $15$ | $10^6$ | Guaranteed $a=b$ |
| $2$ | $20$ | $10^6$ | Guaranteed $a>b$ |
| $3$ | $25$ | $20$ | None |
| $4$ | $40$ | $10^6$ | None |
$\dfrac{a}{2} \equiv a \times 499122177 \pmod {998244353}$, which means that when working modulo $998244353$, you can replace $a \div 2$ with $a \times 499122177$.