404190: GYM101446 D Sequence

The sequence A(x) is built as follows:

• A₁ = x.
• , where is XOR operation.

For a given k count all integer x such that A_k + 1 = A₁ = x holds. Since the answer may be very big, print it modulo 10⁹ + 7.

Input contains one integer k (1 ≤ k ≤ 10⁹).

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

2

3

260

15