「Cfz Round 1」Dead Cells
题目背景
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输入样例 #4
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$。