404190: GYM101446 D Sequence
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
D. Sequencetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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.
InputInput contains one integer k (1 ≤ k ≤ 109).
OutputPrint one integer — answer to the problem modulo 109 + 7. If for the given k there are infinitely many possible x, print - 1 instead.
ExamplesInput2Output
3Input
260Output
15