問題文

以下を満たす数列 A の M 項目を 998244353 で割った余りを求めてください。

• A_{1} = N
• 正整数kに対してA_{k+1} = A_{k} + f(A_{k})

ここで、f(x) で x の x でない最大の約数を表します。

制約

• 2 \leq N \leq 10^{12}
• 1 \leq M \leq 10^{18}
• 入力は全て整数

入力例 1

4 3

出力例 1

9

A_1=4 です。

f(4)=2 より、 A_2=A_1+f(A_1)=4+2=6 です。

f(6)=3 より、 A_3=A_2+f(A_2)=6+3=9 です。

よって、答えるべき値は 9 です。

入力例 2

3 1

出力例 2

3