第一类斯特林数 $\left[ \begin{smallmatrix} n \\ k \end{smallmatrix} \right]$ 是指将 $n$ 个元素排列成恰好 $k$ 个不相交循环的置换数量。其著名的递推关系定义如下：

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

对于 $k > 0$，初始条件为：

$$\left[ \begin{matrix} 0 \\ 0 \end{matrix} \right] = 1 \quad \text{且} \quad \left[ \begin{matrix} n \\ 0 \end{matrix} \right] = \left[ \begin{matrix} 0 \\ n \end{matrix} \right] = 0$$

对于 $n > 0$。

给定四个整数 $n, l, r$ 和 $p$，求以下式子的值：

$$\left( \sum_{k=l}^{r} \left[ \begin{matrix} n \\ k \end{matrix} \right] \right) \pmod 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$ 为质数)。

输出格式

输出一个整数表示答案。

样例

样例输入 1

4 1 4 5

样例输出 1

4

样例输入 2

6 5 5 29

样例输出 2

15

样例输入 3

1000 685 975 999983

样例输出 3

482808