Sumas de Conjuntos.

Submit solution
Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M
Author:
FrankHG
Problem type
Allowed languages
C, C++, Java, JS, Pascal, Python, VB

El granjero John ordenó a sus vacas que buscaran diferentes conjuntos de números que sumaran un número determinado. Las vacas usan solo números que son una potencia entera de 2. Aquí están los posibles conjuntos de números que suman 7:

1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4

Ayude a FJ a contar todas las representaciones posibles para un número entero dado N (1 \leq N \leq 1.000.000).

Entrada

Un entero simple, N.

Ejemplo de Entrada

7

Salida

El número de formas de representar N como la suma indicada. Debido al enorme tamaño potencial de este número, imprima solo los últimos 9 dígitos (en representación de base 10).

Ejemplo de Salida

6

Comments


  • 1
    LeandroGamer  commented on Jan. 31, 2024, 7:13 p.m.

    NO hay que imprimir la respuesta con modulo?


    • 7
      linkyless  commented on Jan. 31, 2024, 9:02 p.m.

      Cito: "Debido al enorme tamaño potencial de este número, imprima solo los últimos 9 dígitos (en representación de base 10)." Espero haber ayudado en algo. Suerte!