P14381 【MX-S9-T4】「LAOI-16」顽疾

> 你怎么像患者的固有资产，催着往事追忆任病情延展。 > > 我用上不眠不休的手段，抵抗梦里你的温暖。

在 ChA 的想象世界，每种疾病都有一个代号。比如 Wa1 就患有顽疾 $(k,w,t)$。 同样地，每种生命体征都有一种代号。Wa1 共测量了 $n$ 次生命体征，设第 $i$（$1 \le i \le n$）个测量结果是 $a_i$。保存测量结果的文件夹按 $a_i$ 升序排序。测量结果序列 $a$ 的风险程度是 $\displaystyle\prod_{i=1}^{n-1} (a_{i+1}-a_{i}+1)^t$，记为 $g(a)$。 定义一个正整数数列 $b$ 满足顽疾 $(k,w,t)$ 的特征，当且仅当下列条件均成立： 1. 对于所有 $1 \le i \le n$，均有 $1 \le b_i \le k$； 2. 对于所有 $1 \le i < n$，均有 $b_i\times b_{i+1}\le w$。 定义 $f(a)$ 为使得 $a_{p_i}$ 满足以上特征的长为 $n$ 的排列 $p$ 的数量。 不幸的是，ChA 完全遗忘了 $a$ 的内容。你只能初步评估 Wa1 的健康情况为 $\displaystyle\sum_{a\in A} f(a)\times g(a)$，其中 $A$ 为全体满足 $\forall i\in [1,n),a_i\le a_{i+1}$ 的序列构成的集合。 为了 Wa1，你需要求出 Wa1 的健康情况。由于这个数可能很大，Wa1 允许你输出对 $10^9+7$ 取模的结果。

仅一行，四个正整数 $n,k,w,t$，含义见题目描述。

共一行，一个整数，表示 Wa1 的健康情况对 $10^9+7$ 取模的结果。

**【样例解释 #1】** - 序列 $a$ 为 $\langle 1,1\rangle$ 时，贡献为 $f(a)\times g(a)=2\times1^2=2$。 - 序列 $a$ 为 $\langle 1,2\rangle$ 时，贡献为 $f(a)\times g(a)=2\times2^2=8$。 - 序列 $a$ 为 $\langle 2,2\rangle$ 时，贡献为 $f(a)\times g(a)=0\times1^2=0$。 其他序列显然 $f(a)=0$，答案为 $2+8+0=10$。 **【样例解释 #2】** 该样例满足测试点 $1\sim 3$ 的约束条件。 **【样例解释 #3】** 该样例满足测试点 $4\sim 7$ 的约束条件。 **【样例解释 #4】** 该样例满足测试点 $8\sim 15$ 的约束条件。 **【样例解释 #5】** 该样例满足测试点 $16\sim 20$ 的约束条件。 **【样例解释 #6】** 该样例满足测试点 $21\sim 30$ 的约束条件。 **【样例解释 #7】** 该样例满足测试点 $31\sim 35$ 的约束条件。 **【样例解释 #8】** 该样例满足测试点 $36\sim 50$ 的约束条件。 **【数据范围】** 本题共 $50$ 个测试点，每个 $2$ 分。 对于所有测试数据，保证： - $1\le n\le 50$； - $1\le k\le 1000$； - $1\le w\le k^2$； - $1\le t\le 5$。 ::cute-table{tuack} |测试点编号|$n \le$|$k \le$|$t \le$| |:--:|:--:|:--:|:--:| |$1\sim 3$|$8$|$8$|$5$| |$4\sim 7$|^|$16$|^| |$8\sim 15$|$30$|$40$|^| |$16\sim 20$|$50$|$100$|$1$| |$21\sim 30$|^|^|$3$| |$31\sim 35$|^|$1000$|$1$| |$36\sim 50$|^|^|$5$|