时空限制

1S/512M

题目描述

已知一个正整数序列 $f$ 满足以下递推关系：

• $f_1 = a!$
• $f_2 = b!$
• $f_n = f_{n - 1} \times f_{n - 2}$ （对于所有 $n \ge 3$）

现在给定正整数 $a, b$ 以及项数 $n$，请你求出 $f_n$ 的因子数量。

由于答案可能非常大，你只需要输出答案模 $998244353$ 的结果。

格式

输入格式

输入仅一行，包含三个正整数 $a, b$ 和 $n$，两两之间由空格隔开。

输出格式

输出一行一个整数，表示 $f[n]$ 的正因子数量模 $998244353$ 的值。

样例

样例输入 #1

2 3 3

样例输出 #1

6

样例解释 #1

根据递推关系：

• $f_1 = 2! = 2$
• $f_2 = 3! = 6$
• $f_3 = f_2 \times f_1 = 6 \times 2 = 12$

$12$ 的所有正因子为 $\{1, 2, 3, 4, 6, 12\}$，共 $6$ 个。 $6 \bmod 998244353 = 6$，故输出 $6$。

样例输入 #2

5 5 5

样例输出 #2

576

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \le a, b \le 10^5$，$1 \le n \le 10^{14}$。