Perfect Sets

Time limit2sMemory limit512 MB

Summary

Count the subsets of {0,...,k} closed under bitwise XOR, where k can be as large as 10^9, modulo 10^9+7.

Level: Medium7 of 10
Topics: Bit manipulation, Combinatorics, Dynamic programming
Solved: No attempts yet

Problem

A non-empty set $S$ of non-negative integers is called perfect when it satisfies the following condition.

For any two integers $a$ and $b$ with $a \in S$ and $b \in S$ ( $a$ and $b$ may be equal), $a \oplus b \in S$ . Here $\oplus$ is the bitwise exclusive or (XOR).

Given an integer $k$ , count the perfect sets whose every element is at most $k$ .

Input

The first line contains an integer $k$ ( $0 \le k \le 10^9$ ).

Output

Print on the first line the number of perfect sets whose every element is at most $k$ , modulo $10^9 + 7$ .

Notes

For $k = 1$ the perfect sets are $\{0\}$ and $\{0, 1\}$ , so there are two of them.

For $k = 4$ they are $\{0\}$ , $\{0, 1\}$ , $\{0, 2\}$ , $\{0, 3\}$ , $\{0, 4\}$ and $\{0, 1, 2, 3\}$ , so there are six of them.

Examples4

Example 1
Input
```
1
```
Expected output
```
2
```
Example 2
Input
```
2
```
Expected output
```
3
```
Example 3
Input
```
3
```
Expected output
```
5
```
Example 4
Input
```
4
```
Expected output
```
6
```