P9577 「Cfz Round 1」Dead Cells

Cidoai 上完生物课后，突发奇想出了这么一道题。 太水了……吧。Cidoai 说着把这道题送给了你，让你去发掘这道题的快乐。

有一天，在第 $0$ 个小时，一个细胞生成了，每过 $a$ 小时，细胞的数量就变成当前的两倍，每过 $b$ 小时，细胞的数量就变成当前的一半（向上取整）。 假如当前时间是 $a$ 和 $b$ 的公倍数，则细胞数量不变。问经过了 $k$ 小时后，细胞个数为多少，答案对 $998244353$ 取模。

一行 $3$ 个正整数，分别表示 $a,b,k$。

一行一个整数，表示答案。

#### 【样例解释 #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$。