设 $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$（两端均包含）之间的元素的顺序。

定义$R(N,K)$为$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$ 取模。