12841284 SUSTech Online Judge
Problem 1284 --Gnisrever Pro [Bonus]

1284: Gnisrever Pro [Bonus]

Time Limit: 7 Sec  Memory Limit: 128 MB
Submit: 57  Solved: 18
[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^{18}, 1 \leq K \leq 5 \times 10^{5}\).

Input

One line gives \(N\) and \(K\), separated by space.

Output

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

Sample Input

5 4

Sample Output

27

HINT

Consider using nodes to represent the sequences of consecutive numbers.


Using splay tree or other balanced tree data structure!


\(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]