Sumas de Conjuntos.

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$ ~N~ $(1 \leq N \leq 1.000.000)$ ~(1 \leq N \leq 1.000.000)~.

Entrada

Un entero simple, $N$ ~N~.

Ejemplo de Entrada

Salida

El número de formas de representar $N$ ~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

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!