Description

有一天，在第 $0$ 个小时，一个细胞生成了，每过 $a$ 小时，细胞的数量就变成当前的两倍，每过 $b$ 小时，细胞的数量就变成当前的一半（向上取整）。

假如当前时间是 $a$ 和 $b$ 的公倍数，则细胞数量不变。问经过了 $k$ 小时后，细胞个数为多少，答案对 $998244353$ 取模。

Input Format

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

Output Format

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

3 4 6

2

4 7 16

4

3 2 5

1

114 5141 919810

62166352

Hint

【样例解释 #1】

第 $1 \sim 6$ 小时的细胞的数量分别为 $1,1,2,1,1,2$。

【数据范围】

对于所有数据，$1 \le a,b,k \le 10^6$。

本题采用捆绑测试。

【提示】

$\dfrac{a}{2} \equiv a \times 499122177 \pmod {998244353}$，即在对 $998244353$ 取模的情况下，您可以用 $a \times 499122177$ 代替 $a \div 2$。