UOJ Logo

NOI.AC

#59. calc

统计

calc

题目描述

给出 $f(i),(1 \leq i \leq n)$ 。

求 $g(i)=\sum\limits_{i_1 \mid i} \sum\limits_{i_2 \mid i_1} \sum\limits_{i_3 \mid i_2} \dots \sum\limits_{i_k \mid i_{k-1}} f(i_k)\ mod\ (10^9+7),(1 \leq i \leq n,i_j \in \mathbb{N}^{+})$ 。

输入格式

第一行两个数 $n, k$ 。

第二行一共 $n$ 个数 $f_i$ 。

输出格式

一行一共 $n$ 个数 $g_i$ 。

样例

输入

23 3
2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

输出

2 9 9 24 9 39 9 50 24 39 9 102 9 39 39 90 9 102 9 102 39 39 9

数据范围

$1 \leq n \leq 500000, 1 \leq k \leq 10^{1000000}, 0 \leq f_i < 10^9+7$ 。

Subtask1 ($30\%$) : $n,k \leq 100$ 。

Subtask2 ($30\%$) : $n \leq 1000, k \leq 10^{1000}$ 。

Subtask3 ($40\%$) :无特殊限制。

时间限制: $1s$ 。

空间限制: $256MB$ 。