TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

60.0% (3/5)

Submission's AC Ratio

50.0% (22/44)

Tags

Description

上個星期,大頭蕃學到了一個新的數論定理:費馬小定理。
大意是說,當P是質數的時候,任何整數X的P-1次方除以P的餘數都會等於1。

大頭蕃覺得太奇妙了!怎能如此神奇,於是他跑去找達克奈特討論這件事情。

經過了一陣雞同鴨講之後,不管大頭蕃說了什麼,達克奈特總是回應「ku ku ku...」,好像某部軍曹動畫裡面帶著螺旋眼鏡的那隻喜歡發出的聲音。

這可讓大頭蕃傷腦筋了,突然,他想到,把這個問題變成程式解題的問題,說不定達克奈特就會回應了!

於是大頭蕃就把它改成了這麼一道題目:


給你m個正整數 X1, X2, ..., Xm,以及k。
請你計算

可是這個題目困擾了大頭蕃好久好久,最後他嘆了一口氣,放棄了。

你能夠幫個忙嗎?

Input Format

輸入檔可能包含多筆測試資料,每一筆佔一列,第一個數字是m,然後有m個數字是X1, X2, ..., Xm,最後是k。(1<=m<=500,000,1<=Xi<231,1<=k<=1,000,000)。
當你發現m=0的時候代表輸入結束。

此外,同一個檔案裡的所有m的總和不超過500,000,並且全部的輸入檔大小總和不超過 5 MB。

Output Format

對於每一筆測試資料,請輸出所求的答案。

Sample Input

3 5 4 3 1234
0

Sample Output

421

Hints

2019/02/28 測資修復 by adrien1018

Problem Source

原TIOJ1324 / TIOJ IOI Warmup III, 2008. Problemsetter: tmt514
EXTREME version of ACM 10692

Subtasks

For Testdata: 0 ~ 0, Score: 16
For Testdata: 1 ~ 1, Score: 16
For Testdata: 2 ~ 2, Score: 16
For Testdata: 3 ~ 3, Score: 16
For Testdata: 4 ~ 4, Score: 16
For Testdata: 5 ~ 5, Score: 20
No. Time Limit (ms) Memory Limit (KiB)
0 2500 65536
1 2500 65536
2 2500 65536
3 2500 65536
4 2500 65536
5 2500 65536