514004 - 序列统计

【题目描述】序列统计（sequence）

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

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

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

可以生成的满足要求的不同的数列有(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)。 【数据规模】 对于10%的数据，1≤N≤1000； 对于30%的数据，3≤M≤100； 对于60%的数据，3≤M≤800； 对于全部的数据，1≤N≤109，3≤M≤8000，M为质数，1≤x≤M-1，输入数据保证集合S中元素不重复。