The Golden Key, or the Adventures of Buratino

Recently, Buratino discovered a data structure known as a segment tree.

A segment tree is essentially a binary tree where each node holds information about a segment defined by boundaries ([l; r]). The root node represents the entire sequence ([1; N]), where (N) is the length of the sequence. For any other node, the following applies: if (l) equals (r), the node is a leaf. Otherwise, it has exactly two children, which contain information about the segments ([l; m]) and ([m+1, r]), respectively. The segment tree is most efficient when the segments ([l; m]) and ([m+1, r]) are of equal length. However, if the segment ([l; r]) has an odd length, it cannot be divided into two equal parts. In such cases, either the left or the right segment will be one unit longer than the other. After each performance, Buratino constructs a segment tree for an array of length (N). Each time, he randomly decides whether to make the left or right segment longer when equal division is not possible.

Your task is to determine how many different segment trees Buratino can create.

Input

The input consists of a single line containing the number (N) ((1 $\le$ N $\le$ 2 $\cdot$ 10^9))—the size of the array for which Buratino will build the segment tree.

Output

Output a single line with the number of different trees Buratino can construct. Since the result can be extremely large, provide the answer modulo (10^9+7).

Examples