Cho ba số nguyên ~n, x, k~. Ta định nghĩa một dãy số ~a_1, a_2, \dots, a_n~ đẹp là dãy có các tính chất sau:

• ~a_i~ là số nguyên không âm;
• ~|a_i - a_{i+1}| \le k~;
• ~a_i~ chứa ít nhất một số trong các số ~x, x+1, x+2, \dots, x+k-1~.

Yêu cầu: Đếm số lượng dãy số đẹp khác nhau (hai dãy khác nhau nếu tồn tại ~i~ sao cho ~a_i~ khác nhau trong hai dãy).

Input

• Dòng đầu tiên chứa số nguyên ~t~ (~t \le 50~) là số testcase;
• ~t~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~n, x, k~ (~1 \le n, k \le 10^9~; ~0 \le x \le 40~).

Output

• Ghi ra ~t~ dòng, mỗi dòng in ra kết quả là số lượng dãy đẹp trong testcase tương ứng (modulo ~10^9 + 7~).