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

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

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

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