---

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\ge 3$.
Let $s_n=F_{2n-1}modN$ and let $t_n=F_{2n}modN$.

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\ge 3$，$F_n=F_{n-1}+F_{n-2}$。
令$s_n=F_{2n-1}modN$，$t_n=F_{2n}modN$。

在初始状态下，整数数组$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$取余。

---