题目背景

在寂静的世界里

我张开手去触碰你

想要挣脱这泥泞笨重的地心引力

我害怕的用力呼吸

期待着不可能发生的奇迹

闭上了双眼

不见 偏离的心率

无助的努力 渐渐地放弃

在残缺的内心里

哭泣着呐喊的我

现在还是散落在月球表面

等时间消逝

沉淀

我在哪里

—— 『月球偏心率』

题目描述

小 L 终于见到了月球的背面，可这里一片荒芜，冷漠乏味。

他想要把这里染成热情的粉红色，为此他翻阅数学书找到了一个函数 $f_t(n)=2^{\omega(n)}n^t$，他要根据这个函数决定染色的过程。

这里的 $\omega(n)$ 为 $n$ 的不同质因子个数，例如 $\omega(1)=0,\omega(2)=1,\omega(8)=1,\omega(6)=2$。

小 L 先把这里划分成了 $n\times n$ 片区域，每个区域倒入不同数量的粉色颜料。具体来说，他会在第 $i$ 行第 $j$ 列的区域内倒入 $f_t(\gcd(i,j))f_t(\operatorname{lcm}(i,j))$ 桶颜料。

不过他已经没有精力去计算了，因此请你直接告诉他总共需要多少桶粉色颜料。

更进一步的，如果上面的答案记成 $F_t(n)$，小 L 会告诉你一个整数 $m\in \{0,1\}$：

• 如果 $m=0$，请你输出 $F_0(n)$。

• 如果 $m=1$，请你输出 $F_0(n),F_1(n)$。

由于答案可能很大，请输出答案对 $10^9+7$ 取模的值。

输入格式

一行两个整数 $n,m$。

输出格式

$m+1$ 个整数代表 $F_0(n)\sim F_m(n)$。

3 1

25 121

1000 0

24870169

10000000000 0

213223517

100000000000000 1

8177545 370603117

提示

• 子任务一 (3 分)：$1\leq n\leq 5000,m\in\{0,1\}$。
• 子任务二 (3 分)：$1\leq n\leq 10^7,m\in\{0,1\}$。
• 子任务三 (8分)：$0\leq n\leq 10^{10},m=0$。
• 子任务四 (8分)：$0\leq n\leq 10^{10},m\in\{0,1\}$。
• 子任务五 (8分)：$0\leq n\leq 10^{12},m\in\{0,1\}$。
• 子任务六 (10分)：$0\leq n\leq 10^{13},m\in\{0,1\}$。
• 子任务七 (13分)：$0\leq n\leq 10^{14},m=0$。
• 子任务八 (14分)：$0\leq n\leq 10^{14},m\in\{0,1\}$。
• 子任务九 (16分)：$1\leq n\leq 10^{16},m=0$。
• 子任务十 (17分)：$1\leq n\leq 10^{15},m\in\{0,1\}$。

时间限制：第九个子任务时间限制 3s，第十个子任务时间限制 3s，其余子任务时间限制 2s。

注：与原题相比，为了卡掉错解，第十个子任务的时间有所调整。