U124868 第〇类循环数·行

兮水姐姐日常无聊，然后她打开了 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

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

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

#### **样例解释** 对于第一组数据：第〇类循环数的第 $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) 以获得帮助。