12671267 SUSTech Online Judge
Problem 1267 --Gnisrever

1267: Gnisrever

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 102  Solved: 23
[Submit][Status][Web Board]

Description

Narnal loves reversing and Fibonacci sequence. When he gets an array with length $$N$$, he would reverse the array in the intervals determined by Fibonacci sequence for $$K$$ times.

Let $$F_{n}$$ is the $$n$$-th Fibonacci number: $$F_{1} = F_{2} = 1, F_{n} = F_{n - 1} + F_{n - 2}$$ for all $$n \geq 3$$.

Let $$s_{n} = F_{2 n − 1} \mod{N}$$ and let $$t_{n} = F_{2 n} \mod{N}$$.

Narnal's reversing always starts with an array of integers $$A = (A[0], \ldots, A[N − 1])$$ where initially every $$A[i]$$ is equal to $$i$$. Now perform $$K$$ successive operations on $$A$$, where the $$j$$-th operation consists of reversing the order of those elements in $$A$$ with indices between $$s_{j}$$ and $$t_{j}$$ (both ends inclusive).

Finally, Narnal's happiness is defined as $$R(N, K) = \sum_{i = 0}^{N - 1} i \times A[i]$$ after $$K$$ operations.

$$1 \leq N \leq 10^{15}, 1 \leq K \leq 5 \times 10^{3}$$.

Input

One line gives $$N$$ and $$K$$, separated by space.

Output

One line with only $$R(N, K) \mod{10^{6}}$$.

Sample Input

5 4

Sample Output

27

HINT

Consider using nodes to represent the sequences of consecutive numbers.

$$R(5, 4) = 27$$ can be seen from the following procedure:
Initial position: $$(0, 1, 2, 3, 4)$$
Step 1 - Reverse $$A[1]$$ to $$A[1]$$: $$(0, 1, 2, 3, 4)$$
Step 2 - Reverse $$A[2]$$ to $$A[3]$$: $$(0, 1, 3, 2, 4)$$
Step 3 - Reverse $$A[0]$$ to $$A[3]$$: $$(2, 3, 1, 0, 4)$$
Step 4 - Reverse $$A[3]$$ to $$A[1]$$: $$(2, 0, 1, 3, 4)$$
$$R(5, 4) = 0 \times 2 + 1 \times 0 + 2 \times 1 + 3 \times 3 + 4 \times 4 = 27$$.

Also, $$R(10^{2}, 10^{2}) = 246597$$.

[Submit][Status]