题目背景

你怎么像患者的固有资产，催着往事追忆任病情延展。

我用上不眠不休的手段，抵抗梦里你的温暖。

题目描述

在 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$ 取模的结果。

2 2 3 2

10

3 4 7 2

532

8 15 114 3

979159471

28 39 1024 2

207170535

48 99 7531 1

974278338

47 97 7864 3

916373488

49 996 959418 1

379260530

50 1000 998244 5

979938753

提示

【样例解释 #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$|