Bài tập | NEU OJ

Bờm vừa học được dấu hiệu chia hết cho 11:

Một số chia hết cho 11 nếu hiệu giữa tổng các chữ số ở vị trí lẻ và vị trí chẵn chia hết cho 11.

Bờm muốn tạo một trò chơi như sau:

Máy tính sinh ra một số nguyên dương N.
Từ các số 1, 2, 3, …, N, máy chọn ra K số phân biệt, sắp xếp chúng theo một thứ tự bất kỳ để tạo thành một dãy ban đầu (gọi là prefix).
Người chơi sẽ phải sử dụng toàn bộ (N−K) số còn lại để ghép tiếp vào cuối prefix, sao cho toàn bộ dãy sau cùng tạo thành một số chia hết cho 11.

Bờm muốn biết:

Có bao nhiêu cách sắp xếp các số còn lại (tức là số hoán vị của (N−K) số chưa dùng) để kết quả cuối cùng chia hết cho 11?

Do kết quả có thể rất lớn, hãy in ra phần dư khi chia cho 1 000 000 007 (10⁹ + 7).

Định dạng đầu vào:
- Dòng 1: Hai số nguyên N và K — tổng số và số phần tử đã dùng.
- Dòng 2: K số nguyên phân biệt trong khoảng [1, N], thể hiện thứ tự mà máy đã chọn sẵn.
Giới hạn:
- 1 ≤ K ≤ N ≤ 10⁵
- Các số trong dòng 2 phân biệt và nằm trong [1, N].
Định dạng đầu ra:
In ra một số nguyên duy nhất — phần dư của số hoán vị hợp lệ (thỏa mãn chia hết cho 11) khi chia cho 1 000 000 007.

solution