Problem Background

After finishing biology class, Cidoai came up with this problem on a whim.

Too easy... right? Cidoai handed this problem to you, inviting you to explore its joy.

Problem Description

One day, at the 0th hour, a cell was generated. Every $a$ hours, the number of cells doubles, and every $b$ hours, the number of cells halves (rounded up).

If the current time is a multiple of both $a$ and $b$, the number of cells remains unchanged. After $k$ hours, how many cells are there, modulo $998244353$?

Input Format

A single line containing three positive integers: $a, b, k$.

Output Format

A single line containing one integer, representing the answer.

Sample Input and Output

Sample Input #1

3 4 6

Sample Output #1

2

Sample Input #2

4 7 16

Sample Output #2

4

Sample Input #3

3 2 5

Sample Output #3

1

Sample Input #4

114 5141 919810

Sample Output #4

62166352

Notes

Sample Explanation #1

The number of cells at hours $1$ through $6$ are $1, 1, 2, 1, 1, 2$ respectively.

Data Range

For all data, $1 \le a, b, k \le 10^6$.

This problem uses subtask testing.

Hints

$\dfrac{a}{2} \equiv a \times 499122177 \pmod {998244353}$, meaning that in modulo $998244353$, you can use $a \times 499122177$ instead of $a \div 2$.

见题面 Input 部分

见题面 Output 部分