当前没有测试数据。

Description

有 $m+1$ 个变量。其中第一个变量 $v_1$ 是有穷变量，它的值是 $p$. 剩余的 $m$ 个变量 $v_2,\ldots,v_{m+1}$ 是无穷变量，它们的值是正无穷大。

为了避免变量溢出，$v_1$ 的值域上限为 $n$，下限为 $0$. 若 $v_1$ 的值为 $n$ 且继续增加值，$v_1$ 的值也仍然会保持为 $n$；同理，若 $v_1$ 的值为 $0$ 且继续减少值，$v_1$ 的值也会仍然保持为 $0$. $v_2,\ldots,v_{m+1}$ 这些变量没有上限和下限。

从初始情况起进行操作。每一轮会按顺序进行如下操作：

1. 执行此操作 $1$ 次：在所有变量中等概率随机选出一个变量，令其值 $+1$.
2. 执行此操作 $k$ 次：在所有变量中等概率随机选出一个变量，令其值 $-1$.

当某一轮结束的时候，若 $v_1$ 的值为零，流程结束；否则继续进入新的一轮的操作。

求流程结束的时候期望进行了多少轮操作。答案可能很大，所以请输出其对 $10^9+7$ 取模的值。

Format

Input

第一行一个正整数 $T\,(1\leq T\leq 10)$ 表示数据组数。

随后对于每组数据，输入一行四个正整数 $n,p,m,k\,(1\leq p\leq n\leq 10^3,1\leq m,k\leq 10^9)$.

Output

对于每组数据输出一行一个正整数表示答案。

Samples

2
2 1 1 1
2 2 1 1

6
8

Limitation

2s, 256MiB.