P9577 "Cfz Round 1" Dead Cells

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.

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$.

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

One line with one integer, representing the answer.

#### 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.** | Subtask ID | Score | $k \le$ | Special Property | |:---:|:---:|:---:|:---:| | $1$ | $15$ | $10^6$ | Guaranteed $a = b$ | | $2$ | $20$ | $10^6$ | Guaranteed $a \gt b$ | | $3$ | $25$ | $20$ | None | | $4$ | $40$ | $10^6$ | None | #### 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