殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲、兩歲又四個月時開始研究「匹配問題」,而現在要講的,是殿壬四歲又六個月大時的故事。
殿壬在四歲又六個月大時,就開始在研究深奧的數學定理,比如說 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$ 的餘數。
輸入的第一行包含兩個整數 $N, K$ ,分別代表多項式的次數,以及 $K$ 。
接下來的一行,有 $N$ 個整數,分別是 $a_{N-1}, a_{N-2}, ......, a_1, a_0$ 。
輸出一個整數,代表 $b_1^ K + b_2^ K + ...... + b_N^ K$ 除以 $10^ 9+7$ 的餘數。
輸出的數字必須介於$[0, 10^ 9 + 7)$ 之間。
No. | Testdata Range | Score |
---|