← 返回题目列表

AtCoder · xmascon24_d

D. 整除幂

中文机器翻译题面 查看原题

配点 : 100 点

各 \lfloor N/i \rfloor 的问题可能没有完善的问题格式。所以这个问题可能有点太人为了。 对于

問題文

正整数 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}.

入力

输入是按以下格式从标准输入给出的。

N A

出力

\displaystyle\sum_{j=1}^k 2024^j g_j 在 10^9+7 后的余数。


入力例 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} 。