#3992. [SDOI2015]序列统计

内存限制:128 MiB 时间限制:30 Sec

题目描述

小C有一个集合S,里面的元素都是小于M的非负整数。他用程序编写了一个数列生成器,可以生成一个长度为N的数
列,数列中的每个数都属于集合S。小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助:
给定整数x,求所有可以生成出的,且满足数列中所有数的乘积mod M的值等于x的不同的数列的有多少个。小C认为
,两个数列{Ai}和{Bi}不同,当且仅当至少存在一个整数i,满足Ai≠Bi。另外,小C认为这个问题的答案可能很大
,因此他只需要你帮助他求出答案mod 1004535809的值就可以了。

输入格式

一行,四个整数,N、M、x、|S|,其中|S|为集合S中元素个数。
第二行,|S|个整数,表示集合S中的所有元素。
1<=N<=10^9,3<=M<=8000,M为质数
0<=x<=M-1,输入数据保证集合S中元素不重复x∈[1,m-1]

集合中的数∈[0,m-1]

输出格式

一行,一个整数,表示你求出的种类数mod 1004535809的值。

样例

样例输入


			
4 3 1 2
1 2

样例输出


			
8
【样例说明】
可以生成的满足要求的不同的数列有(1,1,1,1)、(1,1,2,2)、(1,2,1,2)、(1,2,2,1)、
(2,1,1,2)、(2,1,2,1)、(2,2,1,1)、(2,2,2,2)

数据范围与提示