问题描述

给定 $a$，$b$，求 $1≤x<a^b$ 中有多少个 $x$ 与 $a^b$ 互质。由于答案可能很大，你只需要输出答案对 $998244353$ 取模的结果。

输入格式

输入一行包含两个整数分别表示 $a$，$b$，用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例

2 5

16

12 7

11943936

评测用例规模与约定

对于 $30\%$ 的评测用例，$a^b≤10^6$；

对于 $70\%$ 的评测用例，$a≤10^6$，$b≤10^9$；

对于所有评测用例，$1<a≤10^9$，$1≤b≤10^{18}$。