20621번 - Stirling Number 다국어

문제

The Stirling number of the first kind $\begin{bmatrix} n \\ k \end{bmatrix}$ is the number of permutations of $n$ elements with exactly $k$ disjoint cycles. The well-known recurrence relation is defined as follows: $$\begin{bmatrix} n+1 \\ k \end{bmatrix} = n \begin{bmatrix} n \\ k \end{bmatrix} + \begin{bmatrix} n \\ k-1 \end{bmatrix}$$ for $k>0,ドル with the initial conditions

$$\begin{bmatrix} 0 \\ 0 \end{bmatrix} = 1 \quad {\text{and}} \quad \begin{bmatrix} n \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ n \end{bmatrix} = 0$$ for $n > 0$.

Given four integers, $n,ドル $l,ドル $r,ドル and $p,ドル find the value of $$\left(\sum_{k=l}^{r}{\begin{bmatrix} n \\ k \end{bmatrix}} \right) \bmod p$$ where $p$ is prime.

입력

The first line contains four integers, $n,ドル $l,ドル $r,ドル and $p$ (1ドル \le n \le 10^{18},ドル 0ドル \le l \le r \le n,ドル 2ドル \le p \le 10^6,ドル $p$ is prime).

출력

Output an integer denoting the answer.

제한

힌트