题目描述

已知一个序列 $a$ ，对于任意一个满足 $i > 2$ 的 $i$ ，都有 $a_i = a_{i - 1}\times a_{i - 2}\ \%\ 998244353$ 。

给定 $a_1, a_2, k$ ，求 $a_k$ 。

输入格式

共三个整数， $a_1, a_2, k$ 。

输出格式

一个整数，$a_k$ 。

2 4 3

8

提示/说明

对于 $100\%$ 的数据， $3\le k \le 10^{18}, 0\le a_1, a_2\le 998244352$ 。