#3491. PA2007 Subsets

内存限制:128 MiB 时间限制:20 Sec

题目描述

有一个集合U={1,2,…,n),要从中选择k个元素作为一个子集A。
若a∈A,则要有a*X不属于A,x是一个给定的数。
求可选方案对M取模后的值。
 1< = N< = 10^18,2< = m< = 1000000,0< = K< = 1000,2< = x< = 10。

输入格式

第一行输入N,M,K,X

输出格式

如题

样例

样例输入


			
6 1234 3 2

样例输出


			
9

数据范围与提示