완벽한 집합의 개수

음이 아닌 정수로 이루어진 비어 있지 않은 집합 $S$가 다음 조건을 만족하면 완벽한 집합이라고 한다.

$a \in S$이고 $b \in S$인 임의의 두 정수 $a$, $b$에 대해 ($a$와 $b$는 같아도 된다) $a \oplus b \in S$이다. 여기서 $\oplus$는 비트 단위 배타적 논리합(XOR)이다.

정수 $k$가 주어질 때, 모든 원소가 $k$ 이하인 완벽한 집합의 개수를 구하라.

첫째 줄에 정수 $k$가 주어진다. ($0 \le k \le 10^9$)

모든 원소가 $k$ 이하인 완벽한 집합의 개수를 $10^9 + 7$로 나눈 나머지를 첫째 줄에 출력한다.

$k = 1$이면 완벽한 집합은 $\{0\}$, $\{0, 1\}$의 두 개다.

$k = 4$이면 $\{0\}$, $\{0, 1\}$, $\{0, 2\}$, $\{0, 3\}$, $\{0, 4\}$, $\{0, 1, 2, 3\}$의 여섯 개다.