Sau khi đã giải quyết xong bài toán lì xì, Tít lại bày ra một trò chơi mới. Tít có viên nam châm và muốn xếp chúng vào vị trí có sẵn.
Các vị trí này được xếp thành một hàng ngang và được đánh số từ 1 đến . Khoảng cách giữa hai vị trí liên tiếp là 1 đơn vị. Do kích thước của các viên nam châm là không đáng kể, khoảng cách giữa hai viên nam châm đặt tại vị trí và vị trí được tính là .
Mỗi viên nam châm là một vật thể riêng biệt và có thể phân biệt được với nhau, ngay cả khi chúng có cùng sức hút. Ta đánh số các viên nam châm từ 1 đến . Viên nam châm thứ có sức hút là . Điều này có nghĩa là nó sẽ hút bất kỳ viên nam châm nào khác được đặt trong khoảng cách nhỏ hơn đơn vị.
Tít không muốn có bất kỳ hiện tượng hút nhau nào xảy ra. Do đó, cậu muốn tìm cách xếp tất cả viên nam châm vào vị trí (mỗi vị trí chứa tối đa một viên nam châm) sao cho không có hai viên nam châm nào hút nhau.
Câu hỏi đặt ra là: có bao nhiêu cách sắp xếp thỏa mãn điều kiện trên? Vì kết quả có thể rất lớn, bạn chỉ cần in ra phần dư của nó khi chia cho .
Dữ liệu:
Dòng đầu gồm hai số nguyên dương và () – số lượng nam châm và số lượng vị trí.
Dòng thứ hai chứa số nguyên dương () – biểu diễn sức hút của nam châm.
Kết quả: In ra số cách sắp xếp thỏa mãn mong muốn của Tít sau khi chia lấy dư cho .
Ví dụ:
Dữ liệu:
3 4
1 2 1
Kết quả:
4
Dữ liệu:
4 4
1 1 1 1
Kết quả:
24
Giải thích:
Testcase 1: Ta có 3 nam châm (được đánh số 1, 2, 3 với sức hút tương ứng là 1, 2, 1) và 4 vị trí. Một ví dụ về cách xếp hợp lệ là: nam châm 1 vào vị trí 1, nam châm 2 vào vị trí 4, và nam châm 3 vào vị trí 2.
Khoảng cách giữa nam châm 1 (tại vị trí 1, ) và nam châm 3 (tại vị trí 2, ) là . Không hút nhau vì khoảng cách không nhỏ hơn và không nhỏ hơn .
Tương tự, các cặp khác cũng không hút nhau.
Tổng cộng có 4 cách sắp xếp [1,3,0,2], [3,1,0,2], [2,0,1,3] và [2,0,3,1] trong đó 0 biểu thị vị trí trống còn các số nguyên dương biểu thị số hiệu của nam châm tại vị trí tương ứng.
Testcase 2: Tất cả 4 nam châm đều có sức hút là 1. Khoảng cách nhỏ nhất giữa hai vị trí bất kỳ là 1. Vì điều kiện hút nhau là khoảng_cách < sức_hút (ví dụ: là sai), điều này không bao giờ xảy ra. Do đó, mọi cách xếp 4 nam châm riêng biệt vào 4 vị trí đều hợp lệ. Số cách xếp là .
