扩展斐波那契2
背景
定义函数\(F_n(x)\)如下:
\[F_n(x)=\begin{cases}f_x&(x\leq n)\\k[F_n(x-1)+a_1][F_n(x-2)+a_2]...[F_n(x-n)+a_n]&(x>n)\\\end{cases}\]
其中\(n\)和\(x\)为正整数。
描述
输入\(x\),\(n\),\(k\),\(f_i\)和\(a_i\),求\(F_n(x)\)的值。
由于结果可能很大,求出\(F_n(x)\)%\(65537\)的值即可。
格式
输入格式
三行。
第一行为三个正整数\(x\),\(n\)和\(k\)。
第二行有\(n\)个自然数\(f_i\)。
第三行有\(n\)个自然数\(a_i\)。
\(1\leq x,n\leq 10^5\)
\(0\leq f_i,a_i\leq 10^5\)
输出格式
一行,\(F_n(x)\)%\(65537\)的值。
样例
样例输入
4 2 1
1 2
0 0
样例输出
4
限制
内存256MB,每个测试点1s。