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.


Using linked list reversing!


\(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\).

Source

[Submit][Status]