TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

41.7% (5/12)

Tags

Description

殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲、兩歲又四個月時開始研究「匹配問題」,而現在要講的,是殿壬四歲又六個月大時的故事。

殿壬在四歲又六個月大時,就開始在研究深奧的數學定理,比如說 burnside lemma(據說有會 burnside lemma就可以當上國手的傳說(?))。今天,他遇到了一題有趣的數學問題,想請你幫他解決。

給你一個 $N$ 次整係數多項式 $P(x)=x^ N +a_{N-1}x^ {N-1} + ...... + a_1x + a_0$ ,以及一個正整數 $K$ 。令方程式 $P(x) = 0$ 的根為 $b_1, b_2, ......, b_N$(計算重根),請你算出根的 $K$ 次方和,也就是 $b_1^ K + b_2^ K + \cdots + b_N^ K$ 的值。這邊我們約定 $0 ^ 0 = 1$ 。

由於殿壬很殿(電),所以這個值一定是整數。由於殿壬很殿(電),所以這個數可能很大(或很小!),請你輸出它除以 $10^ 9+7$ 的餘數。

Input Format

輸入的第一行包含兩個整數 $N, K$ ,分別代表多項式的次數,以及 $K$ 。

接下來的一行,有 $N$ 個整數,分別是 $a_{N-1}, a_{N-2}, ......, a_1, a_0$ 。

  • $1 \le N \le 100$
  • $0 \le K \le 10^ {15}$
  • $-10^ 9 \le a_i \le 10^ 9$

Output Format

輸出一個整數,代表 $b_1^ K + b_2^ K + ...... + b_N^ K$ 除以 $10^ 9+7$ 的餘數。
輸出的數字必須介於$[0, 10^ 9 + 7)$ 之間。

Sample Input 1

1 9
1

Sample Output 1

1000000006

Sample Input 2

2 10
-4 4

Sample Output 2

2048

Sample Input 3

6 123456789987654
880301 998244353 8763 7122 514 514514

Sample Output 3

421026052

Hints

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 262144
1 2000 262144 262144
2 2000 262144 262144
3 2000 262144 262144
4 2000 262144 262144
5 2000 262144 262144
6 2000 262144 262144
7 2000 262144 262144
8 2000 262144 262144
9 2000 262144 262144
10 2000 262144 262144
11 2000 262144 262144
12 2000 262144 262144
13 2000 262144 262144
14 2000 262144 262144
15 2000 262144 262144
16 2000 262144 262144
17 2000 262144 262144
18 2000 262144 262144
19 2000 262144 262144
20 2000 262144 262144
21 2000 262144 262144
22 2000 262144 262144
23 2000 262144 262144
24 2000 262144 262144
25 2000 262144 262144
26 2000 262144 262144