Dạo gần đây, phòng Quan hệ Công chúng có báo cáo lại với ban Giám đốc của công ty Ma-tê rằng, người dùng Facenote (một mạng xã hội của công ty) đang phàn nàn rất nhiều về các lỗi vặt và trải nghiệm mà ứng dụng này mang lại. Sau khi phân tích, ban Giám đốc nhận thấy vì công ty mới thành lập, giai đoạn thành lập công ty còn thiếu vốn, nên các lập trình viên được thuê về vẫn còn non kinh nghiệm. Nay ngân sách công ty đã dồi dào, ban Giám đốc quyết định ra lệnh cho phòng Nhân sự thực hiện hai việc; đó là sa thải các lập trình viên không đủ năng lực, và tuyển thêm các lập trình viên mới.

Trong số các vị trí bị thay thế, có một vị trí nằm ngay trong ban Giám đốc là Giám đốc Kỹ thuật. Công ty nhận được hồ sơ của \(n\) ứng viên ứng tuyển cho vị trí này. Các ứng viên được đánh số ngẫu nhiên bởi các số nguyên từ \(1\) tới \(n\). Nhân vật chính của chúng ta hôm nay, anh Hùng, là ứng viên mang số (báo danh) \(1\)!

Vào ngày phỏng vấn, có \(l\) ứng viên tập trung tại công ty. Tất cả \(l\) ứng viên này đều nằm trong số \(n\) người đã nộp hồ sơ kể trên, tuy nhiên có thể có những ứng viên dù đã nộp hồ sơ nhưng lại không đến phỏng vấn. Số báo danh của \(l\) ứng viên này lần lượt là \(a_1, a_2, \ldots, a_l\). Trong đó ứng viên có số báo danh \(a_1\) là người đến sớm nhất, ứng viên có số báo danh \(a_2\) đến sớm thứ hai, \(\ldots\), ứng viên có số báo danh \(a_l\) đến muộn nhất.

Ban Giám đốc cảm thấy tuyển dụng theo quy tắc 36% hơi lâu nên đã bí mật quyết định như sau:

• Đầu tiên, ban Giám đốc chọn ứng viên ưng ý nhất là \(a_1\).
• Tiếp theo, các ứng viên lần lượt vào phỏng vấn theo thứ tự: ở lượt phỏng vấn thứ \(i\), ứng viên \(a_i\) sẽ được phỏng vấn. Nếu ban Giám đốc thấy ứng viên này ấn tượng hơn ứng viên ưng ý nhất ở thời điểm hiện tại, ứng viên ưng ý nhất sẽ được thay đổi thành \(a_i\). Ngược lại, ứng viên ưng ý nhất sẽ giữ nguyên như thời điểm trước đó.
• Do thời gian phỏng vấn có hạn, công ty ra luật nhằm rút gọi thời gian buổi phỏng vấn như sau: Nếu ở một thời điểm nào đó, sau \(k\) lượt phỏng vấn liên tiếp mà ứng viên ưng ý nhất vẫn không đổi, ban Giám đốc sẽ kết thúc buổi phỏng vấn và trao cơ hội cho người này. Các ứng viên còn lại sẽ ra về với lời nhắn: "Bạn rất tốt nhưng chúng tôi rất tiếc. Chúc bạn may mắn lần sau."

Với lợi thế có người quen đang làm ở ban Giám đốc Ma-tê, Hùng được tiết lộ rằng, thực ra số báo danh của các ứng viên không hề ngẫu nhiên! Qua phân tích hồ sơ, công ty đã ngầm đánh số các ứng viên theo quy tắc: ứng viên có năng lực càng tốt sẽ được đánh số càng nhỏ. Và khi phỏng vấn, ứng viên với số báo danh nhỏ hơn chắc chắn sẽ gây ấn tượng tốt hơn với ban Giám đốc. Điều đó có nghĩa là một khi Hùng (người mang số báo danh \(1\)) đã được phỏng vấn, chắc chắn Hùng sẽ được tuyển dụng!

Đêm trước ngày phỏng vấn, vốn là một người ne-vờ-thinh-kinh, Hùng trằn trọc suy nghĩ: chắc chắn mình phải đến rồi, nhưng không biết những người kia ai đến ai không, và họ sẽ đến sớm hay muộn ra sao đây? Rõ ràng, việc Hùng đến quá trễ vẫn có thể khiến Hùng bị loại vì luật "dừng phỏng vấn sau \(k\) lượt" kia, dù anh ta mới là người được đánh giá cao nhất. Hùng tưởng tượng ra nhiều kịch bản xếp hàng khác nhau, mỗi kịch bản lại là một chỉnh hợp của \(n\) ứng viên, và tất nhiên trong chỉnh hợp đó phải có Hùng. Cụ thể hơn:

• Mỗi kịch bản xếp hàng là một danh sách \(a\) gồm \(l\) số nguyên \((a_1, a_2, \dots, a_l)\) thỏa mãn các điều kiện sau:
  • với mọi vị trí \(i\), \(1 \leq a_i \leq n\).
  • tồn tại một vị trí \(j\) sao cho \(a_j = 1\).
  • các số nguyên \(a_1, a_2, \ldots, a_l\) đôi một phân biệt.
• Hai kịch bản \(\alpha = (\alpha_1, \alpha_2, \dots, \alpha_{\mu})\) và \(\beta = (\beta_1, \beta_2, \dots, \beta_{\nu})\) được gọi là khác nhau nếu:
  • \(\mu \neq \nu\); hoặc
  • tồn tại một vị trí \(\iota\) sao cho \(1 \leq \iota \leq min(\mu, \nu)\) và \(\alpha_{\iota} \neq \beta_{\iota}\).

Bây giờ đã là gần 7 giờ 22 phút sáng mà Hùng vẫn chưa ngủ, vì mải duyệt qua hết các kịch bản. Bạn đang nằm cạnh Hùng, muốn động viên Hùng đừng nghĩ nhiều mà nên chợp mắt một tí lấy sức trước phỏng vấn. Vì vậy, bạn hãy tính giúp Hùng số lượng kịch bản xếp hàng sao cho Hùng không được tuyển dụng, mặc dù anh ta là ứng viên xuất sắc nhất.

(Ghi chú: tác giả của kịch bản này có tên gồm đúng \(4\) tiếng, mỗi tiếng gồm đúng \(4\) chữ cái. Việc người này nằm cạnh Hùng là có mục đích gì, thì ban giám khảo chưa điều tra được. Chúng tôi sẽ tiếp tục điều tra về vụ việc này, và đưa đến cho quý vị những thông tin sớm nhất. Mong quý vị đón xem ở những tuần sau.)

Dữ liệu

Vào từ file văn bản recruitment.inp:

• Dòng đầu tiên chứa một số nguyên \(\tau\) là số bộ dữ liệu \((1 \leq \tau \leq 7)\).
• Tiếp theo là \(\tau\) dòng tương ứng với \(\tau\) bộ dữ liệu, mỗi dòng chứa hai số nguyên \(n\) và \(k\) \((1 \leq k \leq n \leq 3000^2)\).

Kết quả

Ghi ra file văn bản recruitment.out:

• Với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên duy nhất là phần dư của số kịch bản khiến Hùng bị loại khi chia cho \(10^9 + 19972207\).

Ràng buộc

• Subtask \(1\) (\(6\) điểm): \(n \leq 5\)
• Subtask \(2\) (\(8\) điểm): \(n \leq 10\)
• Subtask \(3\) (\(18\) điểm): \(n \leq 20\)
• Subtask \(4\) (\(10\) điểm): \(n \leq 80\)
• Subtask \(5\) (\(10\) điểm): \(n \leq 600\)
• Subtask \(6\) (\(14\) điểm): \(n \leq 4000\)
• Subtask \(7\) (\(8\) điểm): \(n \leq 70000\)
• Subtask \(8\) (\(10\) điểm): \(n \leq 300000\)
• Subtask \(9\) (\(16\) điểm): \(n \leq 9000000\)

Ví dụ

2
4 2
6 3

2
114