#H1054. 求和

求和

题目描述

定义 kk 阶广义 Fibonacci\text{Fibonacci} 数列:

fn={an,nki=1kbifni+C,n>kf_n= \begin{cases} a_n,n\leq k \\ \sum\limits_{i=1}^kb_if_{n-i}+C,n>k \end{cases}

特别的,ff 的第 00 项为 00

kk 阶广义 fibonacci\text{fibonacci} 数列中,i=lrfimod20050103\sum\limits_{i=l}^r f_i \bmod 20050103 的值。

输入格式

11 行为 22 个自然数 k,Ck,C
22 行为 kk 个正整数 bib_i
33 行为 kk 个正整数 aia_i
44 行为两个正整数 l,rl,r,意义同上。

输出格式

一行 11 个整数,表示 kkFibonacci\text{Fibonacci} 序列中 i=lrfi\sum\limits_{i=l}^{r} f_i 的值对 2005010320050103 取模的结果。

2 0
1 1
1 1
3 10
141

提示

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

数据规模与约定

对于 100%100\% 的数据,1l,r26311\leq l,r\leq 2^{63}-10k1000\leq k\leq 1000C1080\leq C\leq 10^81ai,bi1081\leq a_i,b_i\leq 10^8