题目背景
Cidoai 上完生物课后，突发奇想出了这么一道题。
太水了……吧。Cidoai 说着把这道题送给了你，让你去发掘这道题的快乐。
题目描述
有一天，在第 $0$ 个小时，一个细胞生成了，每过 $a$ 小时，细胞的数量就变成当前的两倍，每过 $b$ 小时，细胞的数量就变成当前的一半（向上取整）。
假如当前时间是 $a$ 和 $b$ 的公倍数，则细胞数量不变。问经过了 $k$ 小时后，细胞个数为多少，答案对 $998244353$ 取模。
输入格式
一行 $3$ 个正整数，分别表示 $a,b,k$。
输出格式
一行一个整数，表示答案。
样例 1 输入
3 4 6
样例 1 输出
2
样例 2 输入
4 7 16
样例 2 输出
4
样例 3 输入
3 2 5
样例 3 输出
1
样例 3 输入
114 5141 919810
样例 4 输出
62166352
样例 1 解释
第 $1 \sim 6$ 小时的细胞的数量分别为 $1,1,2,1,1,2$。
数据范围
对于所有数据，$1 \le a,b,k \le 10^6$。
本题采用捆绑测试。
| 子任务编号 | 分值 | $k \le$ | 特殊性质 |
|---|---|---|---|
| $1$ | $15$ | $10^6$ | 保证 $a=b$ |
| $2$ | $20$ | $10^6$ | 保证 $a\gt b$ |
| $3$ | $25$ | $20$ | 无 |
| $4$ | $40$ | $10^6$ | 无 |
提示
$\dfrac{a}{2} \equiv a \times 499122177 \pmod {998244353}$，即在对 $998244353$ 取模的情况下，您可以用 $a \times 499122177$ 代替 $a \div 2$。