黑暗爆炸OJ

DARKBZOJ

#4870. [Shoi2017]组合数问题

统计下载数据

Description

Input

第一行有四个整数 n, p, k, r，所有整数含义见问题描述。

1 ≤ n ≤ 10^9, 0 ≤ r < k ≤ 50, 2 ≤ p ≤ 2^30 − 1

Output

一行一个整数代表答案。

Sample Input

2 10007 2 0

Sample Output

8

Hint

Source

黑吉辽沪冀晋六省联考