桃子有一个长度大小为 $n$ 的数组 $a$，她现在有一个长度大小为 $m$ 的滑动窗口。她先用这个窗口从数组的左侧向右侧扫过，每次框选一个由 $m$ 个正整数组成的子数组。一共框选 $n-m+1$次。 例如当 $n=6,m=2$，且 $a=[2,2,3,3,2,3]$ 时。 桃子从左到右划窗获得了 5 个子数组，分别为 $[2,2],[2,3],[3,3],[3,2],[2,3]$。 对于每一个子数组，桃子都想要知道，从该数组中选出一个子序列，并且满足该子序列所有子序列的 gcd = 1，她共有多少种选子序列的方法。

子序列是一个数组删掉某些位置上的元素形成的新数组，当然，你也可以全部删空或者一个也不删。

当且仅当删除元素的位置或者数目不同，我们认为选取子序列的方法不同（即使它们的元素内容全部相同）。 例如数组 $[3,3,2]$，包含的 8 个子序列分别为 ${[],[3],[3],[2],[3,3],[3,2],[3,2],[3,3,2]}$

gcd 表示最大公约数。 若一个序列中所有元素两两互质，则认为这个序列的 gcd 为 1，特别地：序列长度小于等于 1 的序列的 gcd 为 1。

当然，由于这些数字可能比较大，所以要求你输出答案对 $10^{9}+7$ 取余数后的结果即可。

输入格式

第一行输入三个正整数 $n,m,caseNumber$，分别表示数组的大小，划窗的大小，测试点编号。 测试点编号的意义见数据范围

输出格式

输出一行 $n-m+1$个数字表示对于划窗取得的每一个子数组，能够选出符合条件子数组的数目，请输出答案对 $10^{9}+7$ 取余数后的结果，输出的整数之间用一个空格隔开，行末不允许有多余的空格。

4 4 4
2 2 2 2

5

6 6 3
2 2 2 3 3 5

24

10 10 1
16 32 102 7 6 42 15 630 455 97

46

数据范围及约束

本题共有 10 个测试点

对于测试点 1，保证 $n=1000,m=2,2 \leq a_i \leq 1000$

对于测试点 2，保证 $n=10,m=10,2 \leq a_i \leq 1000$

对于测试点 3，保证 $n=1000, m=10, 2 \leq a_i \leq 1000$

对于测试点 4，保证 $n=m,2<=a_i \leq 3$

对于测试点 5，保证 $n=m,2<=a_i \leq 10$

对于测试点 6，保证 $n=m,2 \leq a_i \leq 1000$

对于100%的测试点，保证 $1 \leq m \leq n \leq 2000,2 \leq a_i \leq 1000$

样例解释

对于样例 1，滑动窗口长度为 4 的时候只能得到一个 [2,2,2,2] 的子数组，只有一个空的子序列或者长度为 1 的子序列 gcd 为 1，所以答案为 1。