#1039. BPN - Các cặp số đẹp

Dãy các cặp số nguyên , , …, được gọi là đẹp nếu như thỏa mã hai điều kiện dưới đây:

• với là một số cho trước
• Tất cả các số là khác nhau

Cho số nguyên dương , hãy đếm số lượng dãy cặp đẹp độ dài . Vì con số này có thể rất lớn nên bạn chỉ cần lấy phần dư của nó khi chia cho (1000000007)

Dữ liệu vào:

• Dòng đầu ghi số nguyên là số lượng bộ dữ liệu.
• dòng tiếp theo, mỗi dòng ghi hai số nguyên dương là một bộ dữ liệu.

Dữ liệu ra:

• Với mỗi bộ dữ liệu, in ra kết quả tìm được tương ứng.

Ví dụ:

Dữ liệu vào:

6
1 1
2 1
2 2
3 1
3 2
3 3

Dữ liệu ra:

1
3
0
6
2
0