输入描述:

第一行有四个整数n, p, k, r，所有整数含义见问题描述。
1 ≤ n ≤ 10^9, 0 ≤ r < k ≤ 50, 2 ≤ p ≤ 2^30 − 1

输出描述:

一行一个整数代表答案。

备注:

对于30%的测试点，，p是质数；
对于另外5%的测试点，；
对于另外 5%的测试点，；
对于另外10%的测试点，；
对于另外 15%的测试点，，p是质数；
对于另外15%的测试点，，p是质数；
对于另外 10%的测试点，，p是质数；
对于100%的测试点，。