题目描述

在斐波那契数列中，$F_0 = 0 , F_1 = 1 , F_n = A * F_{n−1} + B * F_{n−2} (n>1)$。

给定整数 $n$，求 $F_n \% \ 998244353$。

输入格式

包含三个整数 $A， B，n(0\le A,B \le 10^{9}，0\le n \le 10^{18})$。

输出格式

一个整数表示结果。

样例

输入样例

1 1 5

输出样例

5