THT C 2021 - Vòng khu vực

Một bài toán trong đại hội Toán-Tin của Thiên hà như sau: Xét các số nguyên dương có dạng \(a_1a_2...a_n\) , trong đó \(a_i\) nhận giá trị \(1\) từ đến \(k\) . Một đoạn chữ số từ vị trí thứ \(L\) đến vị trí thứ \(L + 9\) được gọi là đoạn hoàn hảo nếu:

1) \(a_L + a_{L + 1} + ... + a_{L + 9} = 20\);
2) Các chữ số \(a_L, a_{L + 1}, ..., a_{L + 9}\) có thể chia làm \(2\) nhóm có tổng bằng nhau.

Yêu cầu: Cho \(n, k\) và \(m\) vị trí \(p_1, p_2,..., p_m\), hãy đếm số lượng số nguyên dương có dạng \(a_1a_2...a_n\) (\(a_i\) nhận giá trị từ \(1\) đến \(k\)) mà có \(m\) đoạn hoàn hảo lần lượt bắt đầu từ \(p_1, p_2,..., p_m\).

Input

Vào từ thiết bị vào chuẩn:

• Dòng đầu gồm bốn số nguyên dương \(n, k, m, D\) \((9 < n \le 50; k \le 9; D \le 10^9)\).
• Dòng thứ hai gồm \(m\) số nguyên \(p_1, p_2,..., p_m\) \((1 \le p_1 < p_2 < \dots < p_m \le n - 9)\).

Output

• Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên \(r\), trong đó \(r\) là phần dư của số lượng số thỏa mãn chia cho \(D\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(m = 1\);
• Subtask \(2\) (\(20\%\) số điểm): \(m = 2\);
• Subtask \(3\) (\(60\%\) số điểm): \(m \le 5\).

Example

15 2 2 123
1 3

8

Tham gia đại hội thể thao toàn Thiên hà, đội Trái đất có \(n\) vận động viên tham gia bộ môn cầu lông. Vận động viên thứ \(i\) \((1 \le i \le n)\) có chỉ số thể lực là \(a_i\) và chỉ số kĩ thuật là \(b_i\). Theo thông tin thu nhận được, có \(m (n \le m)\) vận động viên của hành tinh \(Z\) cũng tham gia bộ môn cầu lông, vận động viên thứ \(j (1 \le j \le m)\) có chỉ số thể lực và kĩ thuật tương ứng là \(x_j, y_j\). Đội hành tinh \(Z\) sẽ cử \(n\) vận động viên, gồm các vận động viên liên tiếp từ vận động viên thứ \(k\) đến vận động viên thứ \(k + n - 1\) để đấu với \(n\) vận động viên của đội Trái đất và sẽ thi đấu đúng trận đấu \(n\) (mỗi vận động viên thi đấu một trận). Nếu vận động viên thứ \(i\) của đội Trái đất muốn chắc chắn thắng vận động viên thứ \(j\) của đội hành tinh \(Z\) thì \(a_i > x_j\) và \(b_i > y_j\). Đội Trái đất muốn lên phương án sắp xếp các vận động viên tương ứng thi đấu với vận động viên được cử của đội hành tinh \(Z\) để có nhiều trận
chắc chắn thắng nhất.

Yêu cầu: Cho thông tin về \(n\) vận động viên của đội Trái đất, thông tin \(m\) vận động viên của đội hành tinh \(Z\) và \(Q\) khả năng cử vận động viên bắt đầu từ các vận động viên \(k_1, k_2, ..., k_Q\), với mỗi khả năng cử vận động viên của hành tinh \(Z\), hãy giúp đội Trái đất lên phương án sắp xếp các vận động viên để có nhiều trận chắc chắn thắng nhất.

Input

Vào từ thiết bị vào chuẩn:

• Dòng thứ nhất chứa ba số nguyên dương \(n, m, Q(m \le 10^5; Q \le 100)\);
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n (a_i \le 10^9\) với \(1 \le i \le n)\);
• Dòng thứ ba chứa \(n\) số nguyên dương \(b_1, b_2, ..., b_n (b_i \le 10^9\) với \(1 \le i \le n)\);
• Dòng thứ tư chứa \(m\) số nguyên dương \(x_1, x_2, ..., x_m (x_j \le 10^9\) với \(1 \le j \le m)\);
• Dòng thứ năm chứa \(m\) số nguyên dương \(y_1, y_2, ..., y_m (y_j \le 10^9\) với \(1 \le j \le m)\);
• Dòng cuối chứa \(Q\) số nguyên dương \(k_1, k_2, ..., k_Q(1 \le k_t \le k_t + n - 1 \le m\) với \(1 \le t \le Q)\) .

Output

• Ghi ra thiết bị ra chuẩn gồm \(Q\) dòng, mỗi dòng một số nguyên là số trận chắc chắn thắng lần lượt tương ứng với \(Q\) khả năng cử vận động viên của đội hành tinh \(Z\) trong dữ liệu vào.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 6\);
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 100\);
• Subtask \(3\) (\(25\%\) số điểm): \(n \le 5000\);
• Subtask \(4\) (\(25\%\) số điểm): \(n \le 30000\);

Example

3 6 4
10 20 30
10 20 30
10 20 30 40 50 60
10 20 30 40 50 60
1 2 3 4

2
1
0
0

Huấn luyện viên của đội hành tinh \(Z\) biết rằng, đội Trái Đất đã nắm rõ các chỉ số thể lực và chỉ số kĩ thuật của các vận động viên đội mình, vì vậy ông ta quyết định thay đổi số áo nhằm làm sai lệch những tính toán của đội Trái đất.
Đội hành tinh \(Z\) có \(m\) vận động viên đánh số từ \(1\) tới \(m\), ban đầu vận động viên thứ \(i\) mang số áo là \(i (1 \le i \le m)\)
. Huấn luyện viên chọn \(T\) đoạn, đoạn thứ \(s (1 \le s \le T)\) mô tả bằng cặp số \(L_s, R_s(1 \le L_s \le R_s \le m)\)
, rồi hoán vị số áo của các vận động viên (có thể cả \(m\) vận động viên) sao cho tất cả các vận động viên có số áo nằm trong một trong \(T\) đoạn phải mang số áo khác với số áo ban đầu của mình. Cụ thể, với một vận động viên mang số áo \(i\) mà tồn tại \(s (1 \le s \le T)\) để \(L_s \le i \le R_s\)
thì sau khi hoán vị vận động viên này phải mang số áo khác với số áo ban đầu của mình.

Yêu cầu: Hãy cho biết huấn luyện viên của đội hành tinh \(Z\) có bao nhiêu cách khác nhau để hoán vị số áo cho các vận động viên theo quy tắc trên, hai cách hoán vị số áo được gọi là khác nhau nếu có một vận động viên mang hai số áo khác nhau trong hai cách hoán vị.

Input

Vào từ thiết bị vào chuẩn theo khuôn dạng:

• Dòng đầu chứa số nguyên dương \(m, T\).
• Dòng thứ \(s(1 \le s \le T)\) trong \(T\) dòng tiếp theo chứa hai số nguyên dương \(L_s, R_s (1 \le L_s \le R_s \le m)\).

Output

• Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên duy nhất là số dư của phép chia: số cách hoán vị số áo cho \((10^9 + 7)\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(m \le 10\) và \(T = 0\);
• Subtask \(2\) (\(20\%\) số điểm): \(m \le 10\) và \(T = 1\);
• Subtask \(3\) (\(20\%\) số điểm): \(m \le 10^3\) và \(T = 1; R_1 - L_1 \le 10\);
• Subtask \(4\) (\(20\%\) số điểm): \(m \le 10^3\) và \(T \le 10^3\);
• Subtask \(5\) (\(20\%\) số điểm): \(m \le 10^5\) và \(T \le 10^3\).

Example

3 1
1 2

3