問題文

正整数 m に対して，素数 p であって m が p^2 で割り切れるようなものの個数を f(m) とする．

正整数 N, A が与えられる．集合 \{ \lfloor N/i \rfloor \mid i \in \{1,2,\ldots,N\} \} の元が n_1 < n_2 < \cdots < n_k の k 個であるとする．

j = 1, 2, \ldots, k に対し，\displaystyle\sum_{m=1}^{n_j} f(m)^A を 998244353 で割った余りを g_j とおく．このとき，\displaystyle\sum_{j=1}^k 2024^j g_j を 10^9+7 で割った余りを求めよ．

制約

• 1 \le N \le 10^{14}．
• 1 \le A \le 10^{14}．

入力例 1

15 1

出力例 1

235928270

k = 6,\, (n_1, n_2, n_3, n_4, n_5, n_6) = (1, 2, 3, 5, 7, 15) であり，(g_1, g_2, g_3, g_4, g_5, g_6) = (0, 0, 0, 1, 1, 4) となる．

入力例 2

40 10

出力例 2

236425420

k = 11,\, (n_1, n_2, n_3, n_4, n_5, n_6, n_7, n_8, n_9, n_{10}, n_{11}) = (1, 2, 3, 4, 5, 6, 8, 10, 13, 20, 40) であり，(g_1, g_2, g_3, g_4, g_5, g_6, g_7, g_8, g_9, g_{10}, g_{11}) = (0, 0, 0, 1, 1, 1, 2, 3, 4, 7, 1037) となる．

入力例 3

123456 789

出力例 3

662299501

g_k = 498410667 となる．

入力例 4

100000000000000 100000000000000

出力例 4

913813068

N = 10^{14},\, A = 10^{14} である．