Đếm số lượng bộ số nguyên không âm \((x, y, z)\) thỏa mãn:

Input:

• Dòng đầu tiên ghi số nguyên dương \(T\) là số lượng bộ dữ liệu. Tiếp theo là \(T\) dòng, mỗi dòng ghi 4 số nguyên \(U, d, m, N\)

Output:

• Bộ dữ liệu in ra số lượng tìm được. Con số này có thể rất lớn nên bạn chỉ cần in phần dư của nó khi chia cho \(10^9 + 7\). Giả thiết rằng \(0^0=1\)

Điều kiện:

\(1 \leq T \leq 10\) \(1 \leq U \leq 10 \leq 9\) \(0 \leq d \leq 10^9\) \(1 \leq N \leq 40\) \(0 \leq m\)

Ví dụ:

Input

2
2 2 3 5
1 2013 3 31

Output

4
1

Giải thích

• Case 1:(0, 2, 2), (2, 2, 0), (2, 0, 2), (1, 1, 1)
• Case 2: (1, 1, 1)