Interesting Stirling Task

题号：NC209773
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

The Stirling numbers of the first kind $\left[{n \atop k}\right]$ are defined such that the number of permutations of $n$ elements which contain exactly $k$ permutation cycles (with cycles in opposite directions counted as distinct). The well known recurrence relation is defined as follows:

$\begin{equation}\left[\begin{array}{c} n+1 \\ k \end{array}\right]=n\left[\begin{array}{c} n \\ k \end{array}\right]+\left[\begin{array}{c} n \\ k-1 \end{array}\right]\end{equation}$

for $k>0$ ,with the initial conditions

$\left[0 \atop 0\right]=1\quad {\mbox{and}}\quad \left[{n \atop 0}\right]=\left[{0 \atop n}\right]= 0$

for $n > 0$ .

Roundgod is now solving an interesting task, which gives four integers $n,l,r$ and $p$ , and asks the value of

$\displaystyle \left(\sum_{k=l}^{r}\left[{n \atop k}\right] \right) \bmod p$

where $p$ is prime. Seems Roundgod comes up with the main idea in only one minute. Can you be faster?

输入描述:

The only line contains four integers and   is prime.

输出描述:

Output an integer denoting the answer.

示例1

输入

复制

4 1 4 5

输出

复制

示例2

输入

复制

6 5 5 29

输出

复制