题目描述

定义 $k$ 阶广义 $\text{Fibonacci}$ 数列：

$$f_n= \begin{cases} a_n,n\leq k \\ \sum\limits_{i=1}^kb_if_{n-i}+C,n>k \end{cases}$$

特别的，$f$ 的第 $0$ 项为 $0$。

求 $k$ 阶广义 $\text{fibonacci}$ 数列中，$\sum\limits_{i=l}^r f_i \bmod 20050103$ 的值。

输入格式

第 $1$ 行为 $2$ 个自然数 $k,C$。
第 $2$ 行为 $k$ 个正整数 $b_i$。
第 $3$ 行为 $k$ 个正整数 $a_i$。
第 $4$ 行为两个正整数 $l,r$，意义同上。

输出格式

一行 $1$ 个整数，表示 $k$ 阶 $\text{Fibonacci}$ 序列中 $\sum\limits_{i=l}^{r} f_i$ 的值对 $20050103$ 取模的结果。

2 0
1 1
1 1
3 10

141

提示

$20050103$ 是个质数。请使用较为精细的实现。

数据规模与约定

对于 $100\%$ 的数据，$1\leq l,r\leq 2^{63}-1$，$0\leq k\leq 100$，$0\leq C\leq 10^8$，$1\leq a_i,b_i\leq 10^8$。