### 问题描述 定义 $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$ 是个质数。请使用较为精细的实现。** 性质 $1$：$b_1=1$。 | 子任务编号 | $l,r\leq$ | $k\leq$ | 满足性质 $1$ | 分值 | | :--------: | :--------: | :-----: | :----------: | :--: | | $1$ | $2^{31}-1$ | $1$ | 是 | $4$ | | $2$ | $2^{31}-1$ | $2$ | 是 | $16$ | | $3$ | $2^{31}-1$ | $3$ | 是 | $16$ | | $4$ | $2^{16}$ | $10$ | 否 | $16$ | | $5$ | $2^{32}$ | $20$ | 否 | $16$ | | $6$ | $2^{63}-1$ | $100$ | 否 | $32$ | 以上 $\text{Subtask}$ 如无特殊说明，未标明的数据范围全部按 $100\\%$ 的数据范围给出。 对于 $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$。