스털링 수

제1종 스털링 수 $\begin{bmatrix} n \\ k \end{bmatrix}$은 $n$개의 원소로 이루어진 순열 중 정확히 $k$개의 서로소인 사이클을 갖는 순열의 개수이다. 잘 알려진 점화식은 다음과 같다.

$\begin{bmatrix} n+1 \\ k \end{bmatrix} = n \begin{bmatrix} n \\ k \end{bmatrix} + \begin{bmatrix} n \\ k-1 \end{bmatrix}$

여기서 $k>0$이고, 초기 조건은 다음과 같다.

$\begin{bmatrix} 0 \\ 0 \end{bmatrix} = 1 \quad \text{그리고} \quad \begin{bmatrix} n \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ n \end{bmatrix} = 0$

여기서 $n>0$이다.

네 정수 $n$, $l$, $r$, $p$가 주어질 때, 다음 값을 구하라.

$\left(\sum_{k=l}^{r}{\begin{bmatrix} n \\ k \end{bmatrix}} \right) \bmod p$

여기서 $p$는 소수이다.

첫째 줄에 네 정수 $n$, $l$, $r$, $p$가 주어진다 ($1 \le n \le 10^{18}$, $0 \le l \le r \le n$, $2 \le p \le 10^6$, $p$는 소수).

답을 나타내는 정수 하나를 출력한다.