题目描述

由于出题人实在不会出题了，他只好放一道高中数列题来帮助大家开启愉快的文化课生涯。

数列 $a_n(n\ge 0)$ 由以下几个参数决定：参数 $a,b,c$ 以及 $m$ 次多项式 $f(x)=p_0+p_1x+p_2x^2+\ldots +p_m x^m$。满足：

$$a_i=\begin{cases}a & i=0\\a_{i-1}+f(i)\times a_{\lfloor\frac {i+b}{c}\rfloor} & i\ge 1\end{cases} $$

给定 $n,a,b,c,f$，求 $a_n$。

输入格式

第一行有五个非负整数 $n,a,b,c,m$；

第二行有 $m$ 个非负整数 $p_i$。

输出格式

仅一个非负整数表示答案对 $1004535809$ 取模的结果。

样例

3 1 1 3 2
2 1 1

115

$$a_0=1\\a_1=a_0+(1^2+1+2)\times a_0=5\\a_2=a_1+(2^2+2+2)\times a_1=45\\a_3=a_2+(3^2+3+2)\times a_1=115 $$

数据范围

测试点编号	$n\le$	$m\le$	特殊性质
$1\sim 3$	$10^6$	$20$	无
$4$	$10^7$
$5$	$10^8$
$6$	$10^9$
$7$	$10^{10}$
$8$	$10^{12}$
$9\sim 11$	$10^{18}$	$0$
$12\sim 13$		$1$
$14$		$2$
$15$		$5$
$16\sim 17$		$20$	$c>10^9$
$18\sim 20$			无

对于 $100\%$ 的数据，$n\le 10^{18}$，$m\le 20$，$a,b,c,p_i<1004535809$，$b<c-1$。