4329. Amazing Discovery

单点时限: 1.0 sec

内存限制: 1024 MB

Siyu recently made an amazing discovery. If $a, b, n$ are all positive integers, then

$$ S = (a + \sqrt b)^n + (a - \sqrt b)^n $$

is also a positive integer.

To verify his discovery, please print $S$ modulo $998244353$.

输入格式

The only line contains three integers $a$, $b$, and $n$ ($1 \leq a, b, n \leq 10^9$).

输出格式

Print on a line $S$ modulo $998244353$.

样例

Input
1 2 3
Output
14

118 人解决,210 人已尝试。

150 份提交通过,共有 935 份提交。

4.4 EMB 奖励。

创建: 1 月,2 周前.

修改: 1 月,1 周前.

最后提交: 1 天,21 小时前.

来源: N/A

题目标签