TopCoder

Thumb 343jksfld
ltf0501
願與最重要之人能再次相會。

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

25.0% (1/4)

Description

科學家發現了一種神奇的細菌,他們的繁殖方式很奇怪。這個世界上目前有 $N$ 隻細菌,第 $i$ 隻細菌的體積是 $A_i$ 立方公分。每過一年,對於一隻體積為 $x$ 立方公分的細菌,假設 $x$ 的所有正因數分別是
$$1=d_1<d_2<...<d_k=x$$
那這隻細菌會生出 $k-1$ 隻細菌,體積分別是 $d_1,d_2,...,d_{k-1}$ 立方公分。

科學家發現這種繁殖方式太快了,而且這種細菌是永生的,很快的地球會被這種細菌佔滿!請告訴科學家們,過$K$年後,細菌們的總體積是多少。由於總體積可能太大了,所以請輸出總體積除以 $10^ {9}+7$ 的餘數。

Input Format

輸入共兩行。
輸入的第一行有兩個整數 $N$, $K$ ,$N$ 代表一開始細菌的數量。
第二行包含 $N$ 個正整數,代表 $N$ 隻細菌的體積。

  • $1\leq N\leq 10^ 6$
  • $1\leq A_i\leq 10^ 6$
  • $0\leq K\leq 10^ 9$

Output Format

請輸出一個非負整數代表總體積除以 $10^ 9+7$ 的餘數。

Sample Input

3 1
3 6 8

Sample Output

31

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~15 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 1
6 1000 65536 262144 1
7 1000 65536 262144 1
8 1000 65536 262144 1
9 1000 65536 262144 1
10 1000 65536 262144 1
11 1000 65536 262144 1
12 1000 65536 262144 1
13 1000 65536 262144 1
14 1000 65536 262144 1
15 1000 65536 262144 1