Ban đầu, An có một dãy nhị phân \(S\) độ dài \(n\) gồm toàn các số \(0\). An được thực hiện hai thao tác:

1. Gán giá trị \(0\) cho một đoạn liên tiếp có độ dài đúng bằng \(u\). Cụ thể hơn, bạn được chọn một giá trị \(i\) sao cho \(1 \leq i \leq n-u+1\) và gán \(S_k=0\) với \(i \leq k \leq i+u-1\).
2. Gán giá trị \(1\) cho một đoạn liên tiếp có độ dài đúng bằng \(v\). Cụ thể hơn, bạn được chọn một giá trị \(i\) sao cho \(1 \leq i \leq n-v+1\) và gán \(S_k=1\) với \(i \leq k \leq i+v-1\).

Nếu được thực hiện hai thao tác trên số lần tùy ý, An sẽ tạo ra được tổng cộng bao nhiêu dãy nhị phân khác nhau?

Input

• Dòng đầu tiên chứa số nguyên \(T\) (\(1 \leq T \leq 20\)) là số lượng test.
• Trong \(T\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(n\), \(u\) và \(v\) (\(1 \leq n \leq 2000\), \(1 \leq u, v \leq n\)).

Output

• Gồm \(T\) dòng, dòng thứ \(i\) in ra phần dư trong phép chia đáp án của test thứ \(i\) cho \(10 ^ 9 + 7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(u = n\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 40\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \leq 200\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
1 1 1
2 1 2
2 2 1
2 2 2
9 6 4

2
4
4
2
117