Background

After finishing a biology class on Cidoai, a sudden idea came up, and they created this problem.

"It is too easy... maybe." Cidoai said, and then gave you this problem, asking you to discover the fun in it.

Problem Description

One day, at hour $0$, a cell is created. Every $a$ hours, the number of cells becomes twice the current amount. 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$, then the number of cells does not change. After $k$ hours, how many cells are there? Output the answer modulo $998244353$.

Input Format

One line with $3$ positive integers, representing $a, b, k$.

Output Format

One line with one integer, representing the answer.

3 4 6

2

4 7 16

4

3 2 5

1

114 5141 919810

62166352

Hint

Sample Explanation #1

The numbers of cells from hour $1$ to $6$ are $1, 1, 2, 1, 1, 2$, respectively.

Constraints

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

This problem uses bundled testdata.

Hint

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

Translated by ChatGPT 5