问题描述

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

输入格式

第一行四个整数，N、M、x、|S|，其中|S|为集合S中元素个数。

第二行，|S|个整数，表示集合S中的所有元素。

输出格式

一行一个整数，表示你求出的权值和 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)。

数据范围

• 对于10%的数据，$1≤N≤1000$；
• 对于30%的数据，$3≤M≤100$；
• 对于60%的数据，$3≤M≤800$；
• 对于全部的数据，$1≤N≤10​^9，3≤M≤8000$，M为质数，$1≤x≤M-1$，输入数据保证集合S中元素不重复。

来源

• 2015年山东省队选拔
• 信息学奥赛之数学一本通
• stong9070整理