小 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_iAi≠Bi。另外，小 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≤109, 3≤M≤8000，MMM为质数，1≤x≤M−11 \leq x \leq M-11≤x≤M−1，输入数据保证集合 SSS 中元素不重复。