Problem1316--#2183. 「SDOI2015」序列统计

1316: #2183. 「SDOI2015」序列统计

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 0Submit Num: 0StatisticsShowOff!

Description

小 C 有一个集合 SSS，里面的元素都是小于 MMM 的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为 NNN 的数列，数列中的每个数都属于集合 SSS。

小 C 用这个生成器生成了许多这样的数列。但是小 C 有一个问题需要你的帮助：给定整数 xxx，求所有可以生成出的，且满足数列中所有数的乘积 modM 的值等于 xxx 的不同的数列的有多少个。小 C 认为，两个数列 {Ai}\{A_i\}{A​i​​} 和 {Bi}\{B_i\}{B​i​​} 不同，当且仅当至少存在一个整数 iii，满足 Ai≠BiA_i \neq B_iA​i​​≠B​i​​。另外，小 C 认为这个问题的答案可能很大，因此他只需要你帮助他求出答案 mod1004535809 的值就可以了。

输入格式

第一行，四个整数，NNN、MMM、xxx、∣S∣|S|∣S∣，其中 ∣S∣|S|∣S∣ 为集合 SSS 中元素个数。
第二行，∣S∣|S|∣S∣ 个整数，表示集合 SSS 中的所有元素。

输出格式

一行，一个整数，表示你求出的种类数 mod1004535809 的值。

样例

样例输入

4 3 1 2
1 2

样例输出

8

样例解释

可以生成的满足要求的不同的数列有 (1,1,1,1)(1,1,1,1)(1,1,1,1)、(1,1,2,2)(1,1,2,2)(1,1,2,2)、(1,2,1,2)(1,2,1,2)(1,2,1,2)、(1,2,2,1)(1,2,2,1)(1,2,2,1)、(2,1,1,2)(2,1,1,2)(2,1,1,2)、(2,1,2,1)(2,1,2,1)(2,1,2,1)、(2,2,1,1)(2,2,1,1)(2,2,1,1)、(2,2,2,2)(2,2,2,2)(2,2,2,2)。

数据范围与提示

对于 10%10\%10% 的数据，1≤N≤10001 \leq N \leq 10001≤N≤1000；
对于 30%30\%30% 的数据，3≤M≤1003 \leq M \leq 1003≤M≤100；
对于 60%60\%60% 的数据，3≤M≤8003 \leq M \leq 8003≤M≤800；
对于全部的数据，1≤N≤109, 3≤M≤80001 \leq N \leq 10^9,\ 3 \leq M \leq 80001≤N≤10​9​​, 3≤M≤8000，MMM为质数，1≤x≤M−11 \leq x \leq M-11≤x≤M−1，输入数据保证集合 SSS 中元素不重复。

Source/Category

 
Submit