Description

Format

Input

第一行四个整数N，T，K，OUT，含义如题。

接下来N行，每行一个整数，表示Ai

Output

一个整数，输出方案数。

Samples

3 5 1 3
1
2
3

256

Hint

K,N,Ai<=10^5,<=10^9,

out为大于N的第一个out+1是2的整数幂的数

每个Ai小于out,且互不相同

都有K是一个素数或1,k<=10而且k|(p-1)