시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 11 6 4 66.667%

문제

구사과는 정수론을 공부하고 있다.

음이 아닌 정수로 이루어져 있는 비어있지 않은 집합 S는 다음과 같은 조건을 만족할 때, 완벽한 집합이라고 한다.

임의의 두 정수 a와 b가 a, b ∈ S 일 때, (a와 b는 같아도 된다) (a xor b) ∈ S 이어야 한다.

k가 주어졌을 때, k보다 크지 않은 정수로 이루어진 완벽한 집합의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 k (0 ≤ k ≤ 109)가 주어진다.

출력

첫째 줄에 완벽한 집합의 개수를 109+7로 나눈 나머지를 출력한다.

예제 입력 1

1

예제 출력 1

2

예제 입력 2

2

예제 출력 2

3

예제 입력 3

3

예제 출력 3

5

예제 입력 4

4

예제 출력 4

6

힌트

예제 1의 경우에 정답은 {0}, {0, 1}이 있다.

예제 4의 경우에 정답은 {0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 1, 2, 3}이 있다.

출처