题目描述

Red 在书中找到一个函数 $f(n)$ 满足 $f(1)=1$，而对 $\forall\ n\ge2$，$f(n)$ 为满足 $x+y=n$ 且 $\gcd(x,y)=1$ 的不同有序正整数对 $(x,y)$ 的数量。Red 希望你求出这个函数的值。

但是 Yt 认为这过于简单，他提出了一个新的函数 $g(n)=\sum\limits_{d\mid n}f(\dfrac nd)$，并希望你求出 $F_k(n)=\begin{cases}f(g(n))&k=1\\g(F_{k-1}(n))&k>1\ 且\ k\ 为偶数\\f(F_{k-1}(n))&k>1\ 且\ k\ 为奇数\end{cases}$ 的值，结果对 $998244353$ 取余。

输入格式

一行两个整数，分别表示 $n$ 和 $k$。

输出格式

一行一个整数，表示 $F_k(n)$ 对 $998244353$ 取余后的结果。

样例 1

样例输入

5 1

样例输出

4

样例 2

样例输入

7 2

样例输出

6

数据范围

$1\le n,k\le 10^{12}$