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

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

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

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

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

输入格式

第一行,四个整数,NNNMMMxxx∣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 10001N1000
对于 30%30\%30% 的数据,3≤M≤1003 \leq M \leq 1003M100
对于 60%60\%60% 的数据,3≤M≤8003 \leq M \leq 8003M800
对于全部的数据,1≤N≤109, 3≤M≤80001 \leq N \leq 10^9,\ 3 \leq M \leq 80001N109, 3M8000MMM为质数,1≤x≤M−11 \leq x \leq M-11xM1,输入数据保证集合 SSS 中元素不重复。

Source/Category