第〇类循环数·行

题目背景

兮水姐姐日常无聊,然后她打开了 Minecraft。 > 循环.....要想办法让它转起来。 A few moments later... > 呜呜,红石循环电路到底要怎么做啊..... 好烦好烦,去康学术群惹~ 咕咕学术裙日常: > 铃:XXX 可爱 w 凌:玲酱!贴贴~ 铃:抱~ He Ren:铃酱/qq 铃:He Ren/qq 凌:玲是只属于凌的〇/kk FZ:车...车车? 数学带师:第〇类循环数? XX:/jk /jk /jk 大毒瘤@数学带师(重复若干) 铃:这不就是个 XX 吗?([完整版](https://www.luogu.com.cn/paste/6k6a099f)) (气氛突然开始学术) 兮水:弱弱地问一句,有谁能教下我如何做红石循环电路吗/kel

题目描述

铃给出的第〇类循环数 $f$ 定义如下: - 第 $0$ 行的数均为 $0$。 - 第 $i\in[1,\infty]$ 行第 $0$ 列为 $0$ 到 $2i$ 中的所有 **偶数** 之和。 - 第 $i\in[2,\infty]$ 行第 $j\in[1,i-1]$ 列等于 $\frac{f(i-1,j-1)}{ij}+\frac{f(i-1,j-1)+[j<i-1]f(i-1,j)}{i}+\frac{f(i-1,j-1)}{j}+f(i\!-\!1,j\!-\!1)+[j\!\neq\!i\!-\!1]f(i\!-\!1,j)$。 - 每一行的数都形成了 **无穷个循环**,第 $i$ 行的循环节内容为 $f(i,0),f(i,1)...f(i,i-1)$。 对数学一窍不通的凌想知道第 $k$ 行第 $q$ 列的第〇类循环数是多少,其中 $k$ 为常数,$q$ 等于一个 **一元二次函数** $Q(x)=ax^2+bx+c$。(系数 $a,b,c$ 为 **常整数**,$x$ 为某个指定的值) 但坏坏的铃偷偷吃掉了 $Q(x)$ 的系数,只留下了 $x$ 的数值。为了不让凌太难过,善良的她写下了 **系数取值所在的范围**: $$\begin{cases}a\in[1,n]\\b\in[1,m]\\c\in[1,l]\end{cases}$$ (您可以理解为在给定范围内 **等概率随机一个整数**,且三者 **互不干扰**) 凌想知道第 $k$ 行第 $q$ 列的第〇类循环数 **期望值** 是多少。 连暴力都不会的凌只能傻傻地抱铃,可坏铃不仅不让抱,还提出了一个要求:如果不能在 $1\text s$ 内说出答案,就再也不抱凌了。 这下凌彻底傻眼了,只好向 CP 头子——您 求助。

输入输出格式

输入格式


**本题有多组数据**。 第一行输入一个整数 $T$,表示数据组数。 接下来 $T$ 行,每行输入五个整数,分别表示 $n,m,l,k,x$,如题目所述。

输出格式


输出共 $T$ 行,表示每组询问的答案对 $1004535809$ 取模后的结果。

输入输出样例

输入样例 #1

3
2 2 1 2 1
1 1 3 4 1
15532 10086 114514 1024 0

输出样例 #1

6
334845303
32142711

说明

#### **样例解释** 对于第一组数据:第〇类循环数的第 $1,2$ 行分别为 $\{2,2,2,2\dots\}$ 和 $\{6,6,6,6\dots\}$。查询位置可能的数值有 $\{6,6,6,6\}$,其期望值为 $6$。 对于第二组数据:答案为 $\frac{100}{3}$,对 $1004535809$ 取模得到 $334845303$。 #### **数据范围** **本题采用捆绑测试。** - Subtask 1(1 pts) $\ $:$n,m,l\leq 200$,$k\leq 5\times 10^3$。 - Subtask 2(9 pts) $\ $:$n,m,l\leq 10^9$,$k\leq 5\times 10^3$,满足特殊性质 A。 - Subtask 3(11 pts):$n,m,l\leq 10^9$,$k\leq 5\times 10^3$。 - Subtask 4(19 pts):$n,m,l\leq 10^3$,$k\leq 5\times 10^4$。 - Subtask 5(18 pts):$n,m,l\leq 10^9$,$k\leq 2\times 10^5$,满足特殊性质 A。 - Subtask 6(33 pts):$n,m,l \leq 10^9$,$k\leq 2 \times 10^5$。 - Subtask 7(9 pts) $\ $:无特殊限制。 对于 $100\%$ 的数据:$1\leq n,m,l \leq 10^9$,$1\leq k \leq 2\times 10^6$,$0\leq x \leq 10^{18}$,$1\leq T\leq 5$。 特殊性质 A:满足 $x$ 恰好能被 $k$ 整除。 最后一个测试包较卡常,时限为 $1.5\text s$,请在提交时手动打开 $\text{O2}$ 优化。 由于铃非常喜欢多项式,$k$ **一定为 $2$ 的正整数次幂**。同时模数 $1004535809$ 也是一个特殊的质数,它恰好等于 $479\times 2^{21}+1$,在模 $479\times 2^{21}+1$ 意义下的原根为 $3$。 #### **提示** 如果不会分数取模,请看 [有理数取余](https://www.luogu.com.cn/problem/P2613) 以获得帮助。