Độ khó: Khó (4/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Trên web đọc dữ liệu từ bàn phím (stdin) và in ra màn hình (stdout).

Bài 5. Trò chơi xếp số (GAME11).

Sau khi được học về dấu hiệu chia hết cho 11, Bờm lập trình một trò chơi như sau: Máy tính sinh một số nguyên dương ~n~, sau đó chọn ra ~m~ số phân biệt trong các số ~1, 2, \ldots, n~ và ghép lại theo một thứ tự nào đó. Nhiệm vụ của người chơi là sử dụng tất cả ~n - m~ số còn lại để ghép thành một số chia hết cho 11.

Để tính toán mức độ khó của trò chơi, Bờm muốn đếm số lượng hoán vị các số chưa dùng để ghép tiếp vào dãy mà máy tính đã ghép để tạo thành một số chia hết cho 11.

Yêu cầu: Cho số nguyên dương ~n~ và thứ tự của ~m~ số mà máy tính đã ghép. Hãy đếm số hoán vị các số còn lại để ghép tiếp vào dãy mà máy tính đã ghép để tạo thành một số chia hết cho 11.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên ~n~ và ~m~ ~(0 \le m < n)~.
• Dòng thứ hai gồm ~m~ số nguyên dương đôi một khác nhau có giá trị không vượt quá ~n~ (theo đúng thứ tự máy tính đã ghép; nếu ~m = 0~ thì dòng này để trống).

Kết quả

• Ghi ra phần dư của ~r~ khi chia cho ~10^9 + 7~, với ~r~ là số lượng hoán vị các số còn lại để ghép tiếp vào dãy mà máy tính đã ghép để tạo thành một số chia hết cho 11.

Giới hạn

• ~1 \le n \le 1000~, ~0 \le m < n~ (đề gốc không ghi giới hạn của ~n~; trên web dùng giới hạn này).
• Subtask 1 (35% số test): ~n - m \le 8~.
• Subtask 2 (20% số test): ~n < 100~.
• Subtask 3 (45% số test): không có ràng buộc gì thêm.
• Giới hạn thời gian: 1 giây.

Sample Input 1

3 1
1

Sample Output 1

1

Giải thích

~n = 3~, máy đã ghép ~m = 1~ số là 1. Hai số còn lại là 2 và 3, có ~2! = 2~ hoán vị để ghép tiếp:

• Ghép 2, 3 được số 123, không chia hết cho 11 (~123 = 11 \cdot 11 + 2~).
• Ghép 3, 2 được số 132, chia hết cho 11 (~132 = 11 \cdot 12~).

Vậy có 1 hoán vị thoả.

Sample Input 2

3 0

Sample Output 2

2

Giải thích

Máy chưa ghép số nào. Trong 6 số 123, 132, 213, 231, 312, 321 có 132 và 231 chia hết cho 11 nên đáp án là 2.