题目描述

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

输入格式

第一行四个整数,$\red{N、M、x、|S|}$其中$\red{|S|}$为集合$\red{S}$中元素个数。 第二行,$\red{|S|}$个整数,表示集合$\red{S}$中的所有元素。

输出格式

一行一个整数,表示你求出的权值和$\red{mod\ 1\ 004\ 535\ 809}$的值。

样例

输入样例

4 3 1 2
1 2

输出样例

8

提示

【样例说明】 可以生成的满足要求的不同的数列有$\red{(1,1,1,1)}$、$\red{(1,1,2,2)}$、$\red{(1,2,1,2)}$、$\red{(1,2,2,1)}$、$\red{(2,1,1,2)}$、$\red{(2,1,2,1)}$、$\red{(2,2,1,1)}$、$\red{(2,2,2,2)}$。

【数据规模和约定】 对于$\red{10\%}$的数据,$\red{1≤N≤1 000}$; 对于$\red{30\%}$的数据,$\red{3≤M≤100}$; 对于$\red{60\%}$的数据,$\red{3≤M≤800}$; 对于全部的数据,$\red{1≤N≤10^9}$,$\red{3≤M≤8 000}$,$\red{M}$为质数,$\red{1≤x≤M- 1}$,输人数据保证 集合$\red{S}$中元素不重复。