Para ganar el gran premio del concurso de números de IslaGrande, los concursantes deben calcular de cuántas formas se pueden representar el número entero ~N~ como la suma de números enteros positivos, donde cada sumando no sea menor que otro número ~A~, ni mayor que otro número ~B~. Dos representaciones se consideran la misma si contiene los mismos sumandos, independientemente de su orden.

Por ejemplo, el número ~9~ puede representarse como sumas de números entre ~2~ y ~8~ de las siguientes ~7~ formas: ~2+2+2+3 = 9, 2+2+5 = 9, 2+3+4 = 9, 2+7 = 9, 3+3+3=9, 3+6 = 9, 4+5 = 9~.

Como es un concurso de números, los jueces están interesados en conocer solamente el resto que queda al dividir la cantidad total de representaciones distintas por un número ~M~ dado.

Hacer un programa que permita:

• Leer los números ~N, A, B~, y ~M~.
• Determinar el número representaciones distintas módulo ~M~.
• Escribir hacia la salida el resultado.

Entrada

La entrada contiene en una sola línea los enteros ~N, A, B,~ y ~M~ separados entre si por un espacio en blanco.

Salida

La salida contiene una sola línea donde se escribirá un número entero, el número de representaciones distintas encontradas, módulo ~M~.

Restricciones

• ~1 < A < B < N < 10 000~
• ~1 < M < 10^{15}~

Ejemplos de Entrada

9 2 8 4

Ejemplos de Salida

3

El número total de representaciones distintas es 7,que deja resto 3 al dividirse entre 4