Sumando Números


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 32M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

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


Comments

There are no comments at the moment.