1S 512MB

# calc

### 样例

#### 输入

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\%$) ：无特殊限制。