---

Problem 680

---

Yarra Gnisrever

Let $N$ and $K$ be two positive integers.

$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_{2n - 1} \bmod N$ and let $t_n = F_{2n} \bmod N$.

Start with an array of integers $A = (A[0], \cdots, A[N - 1])$ where initially every $A\text{[}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).

Define $R(N,K)$ to be $\sum_{i = 0}^{N - 1}i \times A\text {[}i]$ after $K$ operations.

For example, $R(5, 4) = 27$, as 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$ and $R(10^4, 10^4) = 249275481640$.

Find $R(10^{18}, 10^6)$ giving your answer modulo $10^9$.

---

组数转逆

任取两个正整数$N$和$K$。

$F_n$是第$n$个斐波那契数：$F_1 = F_2 = 1$，对于所有$n\geq 3$，$F_n = F_{n - 1} + F_{n - 2}$。
令$s_n = F_{2n - 1} \bmod N$，$t_n = F_{2n} \bmod N$。

在初始状态下，整数数组$A = (A[0], \cdots, A[N - 1])$中，$A\text{[}i]$等于$i$。现在，对$A$进行连续的$K$次逆转操作，其中第$j$次操作将数组$A$中下标在$s_j$和$t_j$之间（包含两端）的元素逆序排列。

完成$K$次操作后，记$R(N,K)$为$\sum_{i = 0}^{N - 1}i \times A\text {[}i]$。

例如，$R(5, 4) = 27$，其操作和计算过程如下所示：

初始状态：$(0, 1, 2, 3, 4)$
第$1$步 - 将$A[1]$至$A[1]$逆转：$(0, 1, 2, 3, 4)$
第$2$步 - 将$A[2]$至$A[3]$逆转：$(0, 1, 3, 2, 4)$
第$3$步 - 将$A[0]$至$A[3]$逆转：$(2, 3, 1, 0, 4)$
第$4$步 - 将$A[3]$至$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$

已知，$R(10^2, 10^2) = 246597$，$R(10^4, 10^4) = 249275481640$。

求$R(10^{18}, 10^6)$并将你的答案对$10^9$取余。

---