题目描述

对于一个上界 $n$ 和一个正整数 $m\leq n$，考虑如下随机过程：

• 在 $[1,n]$ 中均匀随机地选择整数 $p$，令 $m\gets \gcd(m,p)$。

该过程会不停执行，直到 $m=1$。令 $E(m,n)$ 表示这个过程的期望执行步数。

对 $1\leq m\leq n$ 的每个 $m$ 求 $E(m,n)$ 在模 $(10^9+7)$ 意义下的值。

输入格式

第一行一个整数 $n$。

输出格式

一行 $n$ 个整数，第 $i$ 个整数表示 $E(i,n)$ 在模 $(10^9+7)$ 意义下的值。

4

0 2 333333337 2

数据范围

对于 $30\%$ 的数据，$1\leq n\leq 4$。

对于 $60\%$ 的数据，$1\leq n\leq 3000$。

对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^5$。