Description

(Those who have not played Hearthstone can skip this paragraph.) Today we explore the interaction between the Hearthstone cards "Healing Rain" (restore 12 health, randomly distributed among all friendly characters) and "Shadowstrike Armor" (whenever a character is healed, deal 1 damage to a random enemy). Suppose you have $m$ minions on the board with infinite remaining health and infinite health capacity (i.e., the difference between max health and current health is also infinite), and your opponent has $k$ Shadowstrike Armors. Your hero has $p$ remaining health and a maximum health of $n$. You cast a "Healing Rain" that can restore an infinite amount of health (instead of 12). We want to know the expected total amount of health restored by the "Healing Rain" before your hero dies (health drops to 0; the mechanics of "Healing Rain" ensure that it will no longer restore health to your hero after this point).

Let us formalize the problem:

You have $m+1$ numbers: the first is $p$, with a minimum value of $0$ and a maximum value of $n$; the remaining $m$ numbers are infinite, having no minimum or maximum values. You can perform any number of rounds of operations. Each round consists of the following steps:

1. Choose one number uniformly at random from those that are not at their maximum value (if none exist, do nothing), and increment it by 1.
2. Perform the following step $k$ times: choose one number uniformly at random from those that are not at their minimum value (if none exist, do nothing), and decrement it by 1.

Find the expected number of rounds until the first number becomes the minimum value $0$.

Input

The input contains multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases.

Each of the next $T$ lines contains four non-negative integers $n, p, m, k$ (see the problem description for their meanings), representing a query.

Output

Output $T$ lines, each containing an integer representing the answer to a query.

If the first number never becomes $0$ regardless of how many rounds are performed, output "-1". Otherwise, it can be proven that the answer is a rational number. Please output the answer modulo $1000000007$. That is, if the answer is $a/b$ (where $a$ and $b$ are coprime positive integers), you should output an integer $x$ such that $0 \le x < 1000000007$ and $a \equiv bx \pmod{1000000007}$.

Examples

Input 1

2
2 1 1 1
2 2 1 1

Output 1

6
8

Constraints

• For 10% of the data: $n \le 3, m, k \le 2$.
• For 20% of the data: $n, m, k \le 5$.
• For 30% of the data: $n, m, k \le 30$.
• For 40% of the data: $n, m, k \le 50$.
• For 50% of the data: $n, m, k \le 200$.
• For 70% of the data: $n \le 200$.
• For 80% of the data: $n \le 500$.
• For 100% of the data: $1 \le T \le 100, 1 \le p \le n \le 1500, 0 \le m, k \le 1000000000$.