J. Multiplicative Array
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Rami has a multiplicative array $$$A=[A_1,\dots,A_n]$$$ of size $$$n$$$. A multiplicative array is an array on which: $$$$$$ \forall u,v\in\{1,\dots,n\}/\quad \gcd(u,v)=1,\quad A_{uv}=(A_u\cdot A_v)\bmod M $$$$$$ with $$$M=10^9+7$$$

He will apply the following algorithm:

  • Set $$$A^{(0)}\leftarrow A$$$
  • For $$$i\in\{1,\dots,m\}:$$$ $$$$$$ \forall k\in \{1,\dots,n\},\quad A^{(i)}_k\leftarrow \sum_{d\mid k}A^{(i-1)}_{d} $$$$$$

He wants to know the content of each element of the final array $$$A^{(m)}$$$, modulo $$$M=10^9+7.$$$

Input
  • The first line contains two integers $$$n,m$$$ with:
    • $$$1 \le n \le 10^6:$$$ The size of the array
    • $$$1\le m\le 10^{18}:$$$ The number of iterations.
  • $$$0 \le A_1,\dots,A_n \le 10^9:$$$ The content of the multiplicative array.

It is guaranteed that there exists $$$i$$$ such that $$$A_i \ne 0$$$

Output

$$$n$$$ integers $$$B_1,\dots,B_n$$$ with $$$B_i=A^{(m)}_i$$$ the content of the final array.

Examples
Input
10 2
1 0 0 0 0 0 0 0 0 0
Output
1 2 2 3 2 4 2 4 3 4
Input
10 5
1 2 3 4 5 6 7 8 9 10
Output
1 7 8 29 10 56 12 93 39 70
Note
  • It is guaranteed that the given array will be multiplicative.
  • In the first test case, Rami will apply two iterations of the algorithm above.
    1. In the first iteration, he will get the array $$$A^{(1)}=[1,1,1,1,1,1,1,1,1,1].$$$
    2. In the second iteration, he will have: $$$$$$ A^{(2)}_k=\sum_{d \mid k} A^{(1)}_d = \sum_{d\mid k} 1 $$$$$$ And with that, $$$\forall k\in\{1,\dots,n\},\quad B_k=A^{(2)}_k$$$ is equal to the number of divisors of $$$k.$$$