Problemas
농부 창호는 그의 소들에게 주어진 수에 대해 생성 가능한 집합 중,
서로 다른 숫자로 이뤄지고 집합의 원소들의 합이 어떤 숫자와 일치하는 가능한 모든 집합을 찾고자 한다.
소들은 2의 제곱꼴의 숫자만을 사용한다(1도 사용 가능하다.) 만들려는 숫자의 합이 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
N이 입력되었을 때 N을 만족하는 서로 다른 집합의 경우의 수를 출력하는 프로그램을 작성하라.
Entrada
입력은 하나의 정수 N(1 ≤ N ≤1,000,000)이 입력된다.
Salida
위에 주어진 조건을 만족하는 가능한 모든 가지수를 출력한다. 너무 숫자가 클 수 있기 때문에 마지막 9자리만 출력하도록 하며, 앞에 0이 나오게 출력하면 안 된다.
Ejemplo
7
6
Debes iniciar sesión para escribir código.