LQDOJ CUP 2022 - Round 2

Nhân dịp \(20\) tháng \(10\), Tèo muốn có một món quà đặc biệt tặng cho bạn nữ duy nhất trong lớp học CP của mình. Tèo dự định sẽ làm một món quà handmade từ một xâu \(A\) gồm \(N\) ký tự. Tèo có thể tạo ra xâu \(B_i = A_iA_{i + 1}\ldots A_NA_1A_2\ldots A_{i - 1}\) bằng tài năng và nghệ thuật của mình.

Tèo thu thập được \(M\) món quà kém chất lượng không được sử dụng vào ngày \(20\) tháng \(10\), mỗi món quà là một xâu khác nhau. Độ xấu của một món quà được làm từ xâu \(A\) được định nghĩa là xâu con dài nhất mà cũng là xâu con của ít nhất một xâu trong \(M\) món quà Tèo thu thập được. Nhắc lại, xâu con là một xâu được tạo từ một đoạn con các ký tự liên tiếp từ xâu ban đầu.

Yêu cầu: Hãy giúp Tèo tạo ra món quà có độ xấu nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(M\) \((N \leq 10 ^ 5\), \(M \leq 10 ^ 4)\) lần lượt là độ dài xâu \(A\) và số xâu thu thập được.
• Dòng thứ hai chứa xâu \(A\) ban đầu.
• Dòng thứ \(i\) trong số \(M\) dòng tiếp theo chứa xâu thứ \(i\) trong số \(M\) xâu thu thập được. Tổng độ dài của các xâu thu thập được là \(T\) \((T \le 10 ^ 5)\).

Biết rằng tất cả các xâu chỉ gồm \(26\) chữ cái Latin in thường.

Output

• In ra độ xấu nhỏ nhất của xâu \(B_i\) Tèo tặng các bạn nữ nhé!

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \le 10 ^ 2\), \(T \le 10 ^ 2\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \le 10 ^ 3\), \(T \le 10 ^ 3\).
• Subtask \(3\) (\(20\%\) số điểm): \(T \le 10 ^ 3\).
• Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

8 9
wqzjuyip
j
i
u
y
p
q
i
uy
z

1

9 3
iuidkunog
uidg
id
iuin

2

10 1
eprwqfntti
ttiwqeprwq

3

Trong một lớp có \(n\) bạn và \(n - 1\) cặp bạn trực tiếp, giữa hai bạn bất kỳ luôn tồn tại một mối quan hệ gián tiếp qua các cặp bạn trung gian này.

Qua một bài kiểm tra, cô giáo nhận thấy bạn thứ \(i\) đã làm được \(a_{i}\) bài của bài kiểm tra. Bằng một phép thần kỳ nào đó, không có hai bạn nào làm được cùng số lượng bài và mỗi bạn (trừ bạn chỉ làm được \(1\) bài) đều có ít nhất một người bạn trực tiếp làm được ít bài hơn.

Cô giáo muốn chấm điểm cho các bạn dựa trên thang điểm nguyên từ \(1 \rightarrow k\) sao cho không có hai bạn nào có cùng điểm. Sẽ rất bất công nếu như trong một cặp bạn trực tiếp, bạn này làm ít bài hơn nhưng lại nhận được điểm cao hơn.

Yêu cầu: Hãy tìm số cách chấm điểm hợp lý giúp cô giáo. Hay nói cách khác, gọi \(b_{i}\) là điểm của bạn thứ \(i\), cô giáo muốn tìm số cách chấm điểm sao cho với mọi cặp bạn trực tiếp gồm bạn \(i\) và bạn \(j\), nếu \(a_{i} > a_{j}\) thì \(b_{i} > b_{j}\) và ngược lại.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \leq n \leq 10^5, 1 \leq k \leq 10^9\)) lần lượt là số bạn và thang điểm của cô giáo.
• Mỗi dòng trong số \(n - 1\) dòng tiếp theo chứa hai số nguyên \(i\) và \(j\) (\(1 \leq i, j \leq n, i \neq j\)) thể hiện một cặp bạn trực tiếp.
• Dòng cuối cùng chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq n, a_i \neq a_j \ \forall i \neq j\)) là số bài làm được mỗi bạn.

Output

• In ra một số nguyên duy nhất là phần dư của số cách chấm điểm hợp lý của cô giáo khi chia cho \(10^9 + 7\).

Scoring

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

Example

1 4
1

4

3 4
1 2
1 3
1 2 3

8

5 5
1 2
2 3
3 4
4 5
1 2 3 4 5

1

Nga vừa mua được một vùng đất lớn và quyết định xây dựng thành phố của chính mình lên đó. Vùng đất được biểu diễn bằng đoạn \([0, n]\) trên trục \(Ox\) và mỗi căn nhà được biểu diễn bằng các điểm nguyên trên đoạn: \(\{x_{1}, x_{2}, \ldots, x_{k}\}\) sao cho \(x_{i} < x_>{j}\) \(\forall 1 \leq i < j \leq k\).

Nga có rất nhiều tiền và muốn xây bao nhiêu căn nhà cũng được. Nga định nghĩa một thành phố hoàn hảo là thành phố thoả mãn điều kiện:

Khoảng cách giữa mọi cặp căn nhà kề nhau phải bằng nhau. Nói cách khác, \(x_{2} - x_{1} = x_{3} - x_{2} = x_{4} - x_{3} = \ldots = x_{k} - x_{k - 1}\).

Nga thắc mắc là với một giá trị \(n\) thì sẽ có bao nhiêu cách tạo nên một thành phố hoàn hảo. Hai cách tạo thành phố được coi là khác nhau khi và chỉ khi ở một cách tạo tồn tại một căn nhà tại một điểm nguyên \(x_i\) trên trục \(Ox\) mà ở cách còn lại thì không có nhà tại điểm đó.

Input

• Dòng đầu chứa một số nguyên \(q\) (\(1 \leq q \leq 10\)) là số lượng câu hỏi cần trả lời.
• Mỗi dòng trong số \(q\) dòng tiếp theo mô tả các câu hỏi của Nga, mỗi dòng gồm duy nhất một số nguyên \(n\) (\(1 \leq n \leq 10^{12}\)) mô tả đoạn nguyên \([0, n]\) cần xây dựng thành phố hoàn hảo ở trên đó.

Output

• In ra một số nguyên tương ứng là phần dư của số cách xây thành phố hoàn hảo đối với câu hỏi tương ứng trong dữ liệu vào khi chia cho \(10^{9} + 7\).

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \leq 10^{3}\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^{6}\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
1
2
3
4
5

3
7
13
22
33