Cell Count Transformation

At time \(0\), exactly one cell is generated. Then, the cell count evolves according to the following rules:

• Every \(a\) hours, if the current time is a multiple of \(a\) but not a multiple of \(b\), the cell count doubles (i.e. it is multiplied by \(2\)).
• Every \(b\) hours, if the current time is a multiple of \(b\) but not a multiple of \(a\), the cell count becomes the ceiling of its half, i.e. \(\lceil\frac{x}{2}\rceil\), where \(x\) is the current number of cells.
• If the current time is a common multiple of both \(a\) and \(b\) (i.e. a multiple of \(\mathrm{lcm}(a,b)\)), no operation is performed and the cell count remains unchanged.

Given three integers \(a\), \(b\), and \(k\) representing the parameters and the total number of hours elapsed, compute the number of cells after \(k\) hours, and output the answer modulo \(998244353\).

Note: All formulas are expressed in \(\LaTeX\) (within \(\$\) symbols).

inputFormat

The input consists of a single line containing three space-separated integers \(a\), \(b\), and \(k\):

• \(a\): the interval (in hours) at which the cell count doubles.
• \(b\): the interval (in hours) at which the cell count becomes \(\lceil\frac{x}{2}\rceil\).
• \(k\): the total number of hours elapsed.

outputFormat

Output a single integer: the number of cells after \(k\) hours modulo \(998244353\).

sample

2 3 6

2