Trên tập số \(\{1, 2, \ldots, n\}\), Alice tiến hành xóa đi số \(k\) \((k \leq n)\) số \(a_{1}, a_{2}, \ldots, a_{k}\) để nhận được tập \(S\). Một cách chọn các số trên tập \(S\) được gọi là cách chọn tối ưu bậc nếu:

• Hiệu hai số bất kì được chọn có giá trị tuyệt đối lớn hơn \(d\);
• Số lượng số được chọn là lớn nhất.
  Ví dụ, trên tập số \(\{1, 2, 3, 4, 5, 6, 7, 8\}\), xóa đi ba số \(2, 3, 8\) được tập \(S = \{1, 4, 5, 6, 7\}\), ba tập \(\{1, 4, 6\}, \{1, 4, 7\}\) và \(\{1, 5, 7\}\) đều là cách chọn tối ưu bậc \(1\).

Yêu cầu: Cho \(n, k, d\) và dãy \(a_{1}, a_{2}, \ldots, a_{k}\), hãy giúp Alice tính số lượng số chọn được trong cách chọn tối ưu bậc \(d\) và số cách chọn tối ưu. Chú ý, hai cách chọn được gọi là khác nhau nếu tồn tại một số của \(S\) thuộc trong cách chọn này nhưng không thuộc trong cách chọn kia.

Input

• Dòng đầu chứa ba số nguyên dương \(n, k, d\) \((k < n \leq 10^{7}, k \leq 10^{5}, d \leq n)\).
• Dòng thứ hai chứa \(k\) số nguyên dương phân biệt \(a_{1}, a_{2}, \ldots, a_{k}\) \((a_{i} \leq n, 1 \leq i \leq k)\).

Output

• Dòng thứ nhất là số lượng số chọn được trong cách chọn tối ưu.
• Dòng thứ hai là số cách chọn tối ưu chia dư cho \((10^{9} + 7)\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n - k \leq 20\).
• Subtask \(2\) (\(25\%\) số điểm): \(n - k \leq 200\).
• Subtask \(3\) (\(25\%\) số điểm): \(n - k \leq 2 \times 10^{5}\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

8 3 1
2 3 8

3
3

Alice muốn đặt mật khẩu cho một ứng dụng mà cô mới xây dựng. Cô đã chọn xâu kí tự \(S\) (kí hiệu \(|S|\) là độ dài xâu \(S\)) và dự định chọn \(K\) đoạn trên xâu \(S\) (các đoạn gồm ít nhất một kí tự và không nhất thiết rời nhau) rồi ghép các đoạn theo một thứ tự nào đó để nhận được xâu đối xứng. Nhắc lại, xâu đối xứng là xâu đọc từ trái qua phải cũng như đọc từ phải qua trái, ví dụ abba, sos là xâu đối xứng, còn xâu abab thì không phải là xâu đối xứng. Alice đã chọn đoạn \(K - 1\), đoạn thứ \(i\) \((1 \leq i < K)\) gồm các kí tự thứ \(L_{i}\) đến kí tự thứ \(R_{i}\) của xâu \(S\) \((1 \leq L_{i} \leq R_{i} \leq |S|)\). Khi chọn đoạn thứ \(K\), Alice muốn chọn một đoạn có độ dài \(m\) mà với đoạn đó Alice có thể ghép với \(K - 1\) đoạn đã chọn theo một thứ tự nào đó để nhận được một xâu đối xứng.

Yêu cầu: Cho xâu \(S\) và \(K - 1\) cặp số \(L_{i}, R_{i}\), hãy đếm số cách chọn đoạn thỏa mãn.

Input

Dòng đầu chứa hai số nguyên dương \(K, m\) \((m \leq S)\);

• Dòng thứ hai chứa xâu \(S\) chỉ gồm các kí tự a đến z \((2^{K} \times |S| \leq 2 \times 10^{5})\);
• Dòng thứ \(i\) \((1 \leq i \leq K - 1)\) trong dòng tiếp theo chứa hai số nguyên dương \(L_{i}, R_{i}\) \((1 \leq L_{i} \leq R_{i} \leq |S|)\).

Output

• Ghi ra một dòng chứa một số là số lượng cách chọn thỏa mãn.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(K = 1, |S| \leq 2000\).
• Subtask \(2\) (\(20\%\) số điểm): \(K = 1\).
• Subtask \(3\) (\(20\%\) số điểm): \(K \leq 7, |S| \leq 2000\).
• Subtask \(4\) (\(20\%\) số điểm): \(K \leq 7\)
• Subtask \(5\) (\(20\%\) số điểm): \(K = 14\).

Example

1 1
abab

4

2 2
abab
2 3

2

Công ty của Alice có \(n\) máy tính, các máy tính được đánh số từ \(1\) đến \(n\). Hiện tại đang có \(m\) \((m \geq n - 1)\) dây nối giữa các máy tính, dây nối thứ \(k\) \((1 \leq k \leq m)\) nối hai máy tính \(u_{k}, v_{k}\) \((u_{k} \neq v_{k}\) và giúp truyền tin theo cả hai chiều giữa hai máy, có thể có nhiều dây nối giữa hai máy tính. Hiện tại, \(n\) máy tính có thể không liên thông với nhau, Alice có thể tháo dây nối để đấu nối lại với mong muốn làm cho \(n\) máy tính liên thông, cụ thể, cô có thể thực hiện:

• Tháo một đầu nối của dây thứ \(k\) để đấu nối sang máy tính khác, hành động này mất chi phí \(c_{k}\);
• Tháo cả hai đầu nối của dây thứ \(k\) để đấu nối sang hai máy tính khác, hành động này mất chi phí \(2 \times c_{k}\).

Yêu cầu: Hãy giúp Alice tính chi phí ít nhất cần thực hiện để liên thông được máy tính.

Input

• Dòng đầu cha hai số nguyên dương \(n, m\) \((n \leq 10^{5}, n - 1 \leq m \leq 2 \times 10^{5})\).
• Dòng thứ \(k\) \((1 \leq k \leq m)\) trong dòng tiếp theo chứa ba số nguyên dương \(u_{k}, v_{k}, c_{k}\) \((c_{k} \leq 10^{6})\).

Output

• Ghi ra một dòng chứa một số là chi phí ít nhất tìm được.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(c_{i} = 1\).
• Subtask \(2\) (\(25\%\) số điểm): \(m, n \leq 1000\).
• Subtask \(3\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 3
1 2 1
1 2 2
1 3 1

0

3 3
1 2 1
1 2 2
1 2 3

1

Một mê cung được mô tả bằng bảng chữ hình chữ nhật kích thước \(m \times n\). Các hàng của bảng được đánh số từ \(1\) đến \(m\), từ trên xuống dưới, các cột của bảng được đánh số từ \(1\) đến \(n\), từ trái qua phải. Ô nằm trên giao của hàng \(i\) và cột \(j\) được gọi là ô \((i, j)\). Mỗi ô của lưới chứa một kí tự ngoặc mở ( hoặc ngoặc đóng ).

Người chơi sẽ xuất phát từ ô \((1, 1)\), quay hướng tới phía ô \((1, n)\) và di chuyển trên bảng. Việc di chuyển phải tuân thủ các quy tắc được mô tả trong hình trên, cụ thể: từ ô đang đứng, căn cứ vào hướng đang hướng tới được chỉ ra bởi mũi tên \(\Rightarrow\), thực hiện bước di chuyển sang ô kề cạnh đang hướng tới, hoặc sang ô kề cạnh nằm bên phải (các hướng có thể di chuyển được chỉ ra bởi các mũi tên \(\rightarrow\)). Mỗi ô chỉ được đi qua nhiều nhất một lần. Người chơi có
thể dừng di chuyển tại một ô nào đó để kết thúc trò chơi.

Khi kết thúc trò chơi, người chơi nhận được một xâu kí tự \(T\) gồm các kí tự trong các ô trên đường đi được xếp liên tiếp nhau. Người chơi giành chiến thắng nếu xâu \(T\) là một biểu thức ngoặc đúng bậc \(k\).

Nhắc lại, định nghĩa biểu thức ngoặc đúng và bậc của biểu thức ngoặc.

• Biểu thức rỗng là biểu thức ngoặc đúng và có bậc bằng \(0\).
• Nếu \(A\) là biểu thức ngoặc đúng có bậc bằng \(k\) thì \((A)\) cũng là một biểu thức ngoặc đúng có bậc bằng \(k + 1\).
• Nếu \(A\) và \(B\) là hai biểu thức ngoặc đúng và có bậc tương ứng là \(k_{1}\) và \(k_{2}\) thì \(AB\) cũng là một biểu thức ngoặc đúng có bậc bằng \(\max(k_{1}, k_{2})\).

Ví dụ, ()(()) là một biểu thức ngoặc đúng có bậc bằng \(2\) còn (()(()))là một biểu thức ngoặc đúng và có bậc bằng \(3\).

Yêu cầu: Cho bảng chữ và số nguyên dương \(k\), đếm số lượng đường đi khác nhau giúp người chơi giành chiến thắng. Hai đường đi được gọi là khác nhau nếu tồn tại một ô thuộc đường đi này nhưng không thuộc đường đi kia.

Input

• Dòng đầu tiên ghi ba số nguyên dương \(m, n, k\) \((m, n \leq 30, k \leq 10)\).
• Tiếp theo là \(m\) dòng mô tả bảng chữ, mỗi dòng chứa một xâu gồm \(n\) kí tự, mỗi kí tự ngoặc mở ( hoặc ngoặc đóng ).

Output

• In ra một dòng là số lượng đường đi đếm được chia dư cho \((10^{9} + 7)\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(m, n \leq 5\).
• Subtask \(2\) (\(25\%\) số điểm): \(k = 1\).
• Subtask \(3\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 3 1
())
)()
)))

4

Alice có \(n\) món đồ cổ và muốn bán tất cả trong \(m\) ngày. Cô đã tìm hiểu và biết được là \(c_{it}\) số tiền mà cô sẽ nhận được nếu bán món đồ \(i\) \((1 \leq i \leq n)\) ở ngày \(t\) \((1 \leq t \leq m)\) hoặc \(c_{it} = -1\) nếu không ai muốn mua món đồ \(i\) ở ngày \(t\). Một số món đồ phải được bán trước một số món đồ khác, có \(k\) ràng buộc như vậy, mỗi ràng buộc có dạng \((u, v)\) và có nghĩa là món đồ \(u\) phải được bán trước ít nhất một ngày so với ngày bán món đồ \(v\). Alice muốn lên kế hoạch bán tối ưu để có thể thu được nhiều tiền nhất. Chú ý rằng, mỗi ngày Alice có thể bán nhiều hơn một món đồ miễn là các món đồ liên quan đến ràng buộc bán trước các món đồ này đều đã được bán ở các ngày trước.

Yêu cầu: Giúp Alice tính số tiền nhiều nhất có thể nhận được khi bán tối ưu tất cả các món đồ.

Input

• Dòng đầu tiên ghi ba số nguyên dương \(n, m, k\) \((n, m, k \leq 100)\).
• Tiếp theo là \(n\) dòng, dòng thứ \(i\) \((1 \leq i \leq n)\) chứa \(m\) số nguyên \(c_{i1}, c_{i2}, \ldots, c_{im}\) \((-1 \leq c_{it} \leq 100)\).
• Tiếp theo là dòng \(k\), mỗi dòng chứa hai số nguyên dương \(u, v\) \((1 \leq u, v \leq n)\) cho biết món đồ phải \(u\) trước ít nhất một ngày so với ngày bán món đồ \(v\).

Dữ liệu đảm bảo có cách bán hết cả \(n\) món đồ.

Output

• Ghi ra một dòng là số tiền nhiều nhất có thể nhận được khi bán tối ưu tất cả các món đồ.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): $n \leq 15#.
• Subtask \(2\) (\(35\%\) số điểm): Trong \(k\) ràng buộc không có hai ràng buộc nào có cùng giá trị \(v\);
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 2 2
100 -1
100 80
100 90
1 2
1 3

270