TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

33.3% (1/3)

Tags

Description


加百列在地球天國魔法競賽中嶄獲佳績,最後來到了最終決賽:全時空魔法競賽。
在比賽中她看了看題目。
「PA、PB、PD直接DFS就好了。」
「PE建完凸包然後對每條邊建一次矩形就好了。」
「PF好好Rolling Hash就好了。」
「PG不就是兩倍樹權和減掉直徑嗎?」
「PH直接二分搜答案後Dinic配上bitmask或時間剪枝就好了。」
不過問題來了,加百列原本以為PC的題目是「一個長度為$n$的字串由$k$種字元組成,給你每種字元的個數,求這個字串有多少個相鄰字元相異的期望值」。
如果是這樣的話,就直接窮舉每個位置相異的期望值然後加總就可以了。
然而實際的題目卻是「給你$k$種不同的字元和每個字元可以使用奇數個、偶數個、或是沒限制,有$q$筆詢問,每次問你說在條件下有多少個長度為$n$的字串符合條件」。
加百列所思右想就是不得其解,剛好你也把其他題目都AC了,只差這一題了,如果解出來的話搞不好可以破台喔><

Input Format

第一行有一個正整數$k$表示有$k$種不同的字元。
第二行有$k$個整數,其中$a_i$是$0$的話表示第$i$種字元只能使用偶數次、是$1$的話只能使用奇數次、是$2$的話則是沒限制。
第三行有一個整數$q$表示有$q$筆詢問。
接下來$q$行每行有一個正整數$n$表示詢問長度為$n$且符合條件的字串有多少個。

Output Format

對於每個詢問,輸出一個正整數表示符合條件的字串有幾個。
由於答案可能過大,請輸出答案除以$ 10^ 9 + 9$的餘數。
請注意,這題和幫幫米桑吧那題不一樣,是模$10^ 9 + 9$,不要搞錯囉><

Sample Input

5
2 0 0 2 2
3
1
2
3

Sample Output

3
11
45

Hints

subtask $0 \sim 2 : k \leq 2 ,\ q \leq 2 ,\ n \leq 2$
subtask $3 \sim 5 : k \leq 5 ,\ q \leq 5 ,\ n \leq 5$
subtask $6 \sim 7 : k \leq 200 ,\ q \leq 1000 ,\ n \leq 1000$
subtask $8 \sim 9 : k \leq 10^ 3 ,\ q \leq 10^ 4 ,\ n \leq 10^ {18}$
範測說明:
將第$i$種字元記做$i$。
那麼1、4、5都沒有限制,2、3則是只能使用偶數次。
長度為1符合條件的字串有:1、4、5,因為2、3只能使用偶數個所以不符合條件。
長度為2符合條件的字串有:11、14、15、41、44、45、51、54、55、22、33,共11個。

Problem Source

Problem set and Description by PolarisChiba

Subtasks

For Testdata: 0 ~ 2, Score: 30
For Testdata: 3 ~ 5, Score: 30
For Testdata: 6 ~ 7, Score: 20
For Testdata: 8 ~ 9, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 65536
1 10000 65536 65536
2 10000 65536 65536
3 10000 65536 65536
4 10000 65536 65536
5 10000 65536 65536
6 10000 65536 65536
7 10000 65536 65536
8 10000 65536 65536
9 10000 65536 65536