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

138 人解决,235 人已尝试。

171 份提交通过,共有 1032 份提交。

4.2 EMB 奖励。

创建: 3 年,2 月前.

修改: 3 年,1 月前.

最后提交: 11 月,3 周前.

来源: N/A

题目标签