题意：给定 $n, k$，求
$$ \sum_{x=1}^{n} \operatorname{lcm}(x, x+1, \dots, x+k) $$ 对 $10^9 + 7$ 取模的结果。

• $1 \le n \le 10^{18}$
• $0 \le k \le 30$

注意到
$$ \operatorname{lcm}(x, \dots, x+k) = \frac{1}{c} \times x(x+1)\cdots(x+k), $$ 其中 $c$ 是个正整数。

考虑我们会如何给 $\frac{1}{c}$ 进行贡献。对于质数 $p$，设 $e$ 为最大整数使得 $p^e \le k$，那么对于模 $p^e$ 相同的 $x$，他对 $\frac{1}{c}$ 的贡献都是一样的。

设
$$ L = \operatorname{lcm}(1, \dots, k), $$ 也就是说 $\frac{1}{c}$ 的值是以 $L$ 为一个循环的。

如果 $L$ 比较小，那么可以暴力枚举。不过 $L$ 可以到达 $10^{12}$ 级别。

考虑对于一个 $p^e$，他的所有对 $\frac{1}{c}$ 的贡献中，有很多都是相同的，设为 $\frac{1}{c_0}$。那么我们先假定所有贡献都是 $\frac{1}{c_0}$（即模 $1$ 为 $0$ 时贡献都是 $\frac{1}{c_0}$），然后把其贡献序列 $a_0, \dots, a_{p^e-1}$ 的每一项都减去 $\frac{1}{c_0}$，此时对于 $a$ 所有非零项，单独算贡献即可（比如说在模 $p^e$ 为 $r$ 时这一项为 $a_r$ 且非零，那么在模 $p^e$ 为 $r$ 时再多个贡献是 $a_r$ 即可）。

显然可以把 $\frac{1}{c_0}$ 设为贡献中出现最多的数。这样的话，不同的余数个数就变少了。数量大约是 $10^8$ 级别，不妨记为 $M$。

不过这样还是不行。于是考虑折半搜索的技巧，对于所有的质数，可以分在左半边或者右半边，于是可以把 $M$ 分成两个相差不大的数 $M_1, M_2$。此时 $M_1, M_2$ 都可以看作是 $\sqrt{M}$ 级别的数。质数也可以看作是左边五个，右边五个。

考虑 $O(2^{10})$ 枚举模数 $P$（由于每个质数都有两种情况的模数，一个为 $1$，另一个为 $p^e$，因此总共有 $2^{10}$ 种情况）。然后考虑把左右两边的余数用 CRT 合并起来。枚举左边的一个数 $r_1$，可以发现，对于一个连续段的右边的数 $r_2$，贡献都是类似的。

具体来说，对于每个连续段，答案都是形如 $$ c_1 c_2 \sum_{i=0}^{\text{lim}-1} (iP + r_1 + r_2)^{k+1}. $$

将其二项式定理展开后，就是几个东西的卷积的形式，维护前缀和、自然数幂和等信息后，就可以 $O(k^2)$ 合并了。

由于可能出现 $r_1 + r_2 \ge P$ 的情况，以及自然数幂和的上界 $\text{lim}$ 可能有 $1$ 的偏差，因此会被分成若干个连续段。不过对于每个 $r_1$，一共有 $O(1)$ 个这种连续段，所以不影响复杂度。

因此总的复杂度为：

$$ O(2^5 \sqrt{M} k^2). $$