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

36.7% (22/60)

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

No. Testdata Range Score
1 0 16
2 1 16
3 2 16
4 3 16
5 4 16
6 5 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2500 65536 262144 1
1 2500 65536 262144 2
2 2500 65536 262144 3
3 2500 65536 262144 4
4 2500 65536 262144 5
5 2500 65536 262144 6