luogu#P3321. [SDOI2015] 序列统计
[SDOI2015] 序列统计
题目描述
小C有一个集合 ,里面的元素都是小于 的非负整数。他用程序编写了一个数列生成器,可以生成一个长度为 的数列,数列中的每个数都属于集合 。
小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助:给定整数 ,求所有可以生成出的,且满足数列中所有数的乘积 的值等于 的不同的数列的有多少个。
小C认为,两个数列 和 不同,当且仅当 。另外,小C认为这个问题的答案可能很大,因此他只需要你帮助他求出答案对 取模的值就可以了。
输入格式
一行,四个整数,,其中 为集合 中元素个数。
第二行, 个整数,表示集合 中的所有元素。
输出格式
一行一个整数表示答案。
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)。
【数据规模和约定】
对于 的数据,;
对于 的数据,;
对于 的数据,;
对于 的数据,,,。
为质数,输入数据保证集合 中元素不重复。