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