Cho ba số nguyên \(n,k,x\). Ta định nghĩa một dãy số \(a_1,a_2,…,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) |≤k\);

• \(a\) chứa ít nhất một số trong các số \(x,x+1,x+2,…,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).

Dữ liệu: Vào từ tệp văn bản MBSEQ1.INP:

• Dòng đầu tiên chứa số nguyên \(t (t≤50\)) là số testcase;

• \(t\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(n,x,k (1≤n,k≤10^9;0≤x≤40).\)

Kết quả: Ghi ra tệp văn bản MBSEQ1.OUT

• gồm \(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\)).

Ràng buộc:

• 30% số test ứng với 30% số điểm của bài có \(x=0;\)

• 30% số test ứng với 30% số điểm của bài có \(n≤10^5;\)

• 40% số test không có ràng buộc gì thêm

Sample Input

4
3 0 1
1 0 25
4 0 2

Sample Output

9
25
250