D. Sequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The sequence A(x) is built as follows:

  • A1 = x.
  • , where is XOR operation.

For a given k count all integer x such that Ak + 1 = A1 = x holds. Since the answer may be very big, print it modulo 109 + 7.

Input

Input contains one integer k (1 ≤ k ≤ 109).

Output

Print one integer — answer to the problem modulo 109 + 7. If for the given k there are infinitely many possible x, print  - 1 instead.

Examples
Input
2
Output
3
Input
260
Output
15