Hôm nay là ngày Tuấn bắt đầu học các thuật toán cơ bản về xâu ở trên lớp và được giao bài tập về nhà. Tuấn giải những bài đầu rất nhanh nhưng đến bài cuối cậu đã gặp phải một bài tập khá hóc búa, nghĩ mãi không ra. Cho một xâu ~S~ có độ dài ~m~ và một số nguyên dương ~n~ ~(m \le n \le 5000)~.

Từ xâu ~S~, ta có thể tạo ra xâu mới theo quy tắc sau: thêm xâu ~T~ là tiền tố của ~S~ vào cuối xâu ~S~.

Ví dụ: Với xâu ~S = \texttt{baacb}~, các xâu có thể tạo ra có độ dài ~n = 8~ là ~\texttt{"baacbbbb", "baacbbba", "baacbbab", "baacbbaa"}~.

Đếm số xâu phân biệt độ dài ~n~ có thể tạo ra, in ra kết quả là phần dư khi chia cho ~10^9 + 7~.

Tuấn đang vô cùng bất lực khi đã dành hàng giờ để suy nghĩ nhưng vẫn chưa có ý tưởng gì. Bạn hãy giúp Tuấn giải bài tập trên nhé!

Input

• Dòng thứ nhất gồm 2 số nguyên dương ~m~ và ~n~ (~m \le n \le 5000~).

• Dòng thứ hai gồm một xâu ~S~ có độ dài ~m~.

Output

• Một số nguyên duy nhất là kết quả tìm được

Sample Input 1

5 8
baacb

Sample Output 1

4

Notes

Với xâu ~S = baacb~, các xâu có thể tạo ra có độ dài ~n = 8~ là:

• baacbbbb

• baacbbba

• baacbbab

• baacbbaa

Cho bốn số nguyên dương ~L~, ~R~, ~X~, ~K~, và một mảng ~v~ có ~|X|~ phần tử (~|X|~ là số chữ số của số ~X~).

Ta định nghĩa độ đẹp của số nguyên dương ~S~ là ~\sum\limits_{i = 1}^{|X|} cnt(i, S) * v_i~, trong đó ~cnt(i, S)~ là số lần xuất hiện của tiền tố độ dài ~i~ của ~X~ trong số ~S~.

Định nghĩa tiền tố độ dài ~i~ của một số ~A~ là số tạo bởi ~i~ chữ số đầu tiên của số ~A~ (ví dụ tiền tố độ dài ~1~ của số ~2306~ là ~2~, tiền tố độ dài ~2~ là ~23~).

Một số được gọi là xấu nếu độ đẹp của nó không lớn hơn ~K~.

Yêu cầu: Đếm số lượng số xấu trong đoạn ~[L, R]~

Input

Gồm hai dòng:

• Dòng thứ nhất chứa ~4~ số nguyên dương ~L~, ~R~, ~X~, và ~K~.
• Dòng thứ hai chứa ~|X|~ số ~v_1, v_2, \dots, v_{|X|}~.

Giới hạn:

• ~1 \leq L \leq R < 10^{200}~
• ~1 \leq X < 10^{20}~
• ~1 \leq K \leq 10^4~
• ~1 \leq v_i \leq 100~ ~\forall~ ~1 \leq i \leq |X|~

Output

Gồm một số nguyên duy nhất là số lượng số xấu trong đoạn ~[L, R]~ lấy phần dư trong phép chia cho ~10^9+7~.

Sample Input 1

203 427 75 3
2 2

Sample Output 1

221

Cho ba số nguyên ~L~, ~R~, ~k~, hãy đếm số lượng số đẹp trong đoạn ~[L, R]~. Số đẹp là số nguyên mà biểu diễn thập phân của nó chứa số nguyên ~k~ (ví dụ nếu ~k = 13~ thì ta có các số đẹp là ~12\textbf{13}~, ~1\textbf{13}~, ~234\textbf{13}~, ~\dots~).

Input

Gồm ba dòng, mỗi dòng lần lượt chứa số nguyên ~L~, ~R~, ~k~.

Điều kiện:

• ~1 \le L \le R \le 10^{100000}~

• ~1 \le k \le R~

• ~log_{10}(k) \cdot log_{10}(R) \le 5 \cdot 10^6~

Output

Gồm một số nguyên duy nhất là số lượng số đẹp trong khoảng ~[L, R]~ lấy phần dư với phép chia ~10^9+7~.

Scoring

Subtask ~1~ ~(20\%)~:

• ~k \le R \le 10^9~

• ~R - L \le 10^6~

Subtask ~2~ ~(80\%)~: Không có giới hạn gì thêm.

Sample Input 1

1
142
13

Sample Output 1

12

Tại xứ sở thần kỳ có một chiếc đồng hồ phép thuật có ~n~ kim hoàn toàn giống nhau (bao gồm cả độ dài). Do đã hoạt động lâu năm và không được tu sửa nên tất cả các dấu mốc thời gian của đồng hồ đã bị phai mờ. Bởi lẽ đó mà việc theo dõi thời gian bỗng cực kỳ khó khăn, khiến đời sống người dân không kém phần phiền toái. Chính vì thế, chính phủ của xứ sở đang cần tuyển dụng những nhà quan trắc thời gian mới để hỗ trợ người dân.

Để ứng tuyển trở thành một nhà quan trắc thời gian, các ứng viên cần phải vượt qua bài sát hạch được thiết kế bởi các nhà toán thời gian học của xứ sở. Nội dung của bài sát hạch rất đơn giản - các ứng viên sẽ được giao hai tấm ảnh của chiếc đồng hồ thần kì tại hai thời điểm bất kỳ trong ngày, và họ cần xác định nhanh chóng liệu hai tấm ảnh đó có thể đã được chụp tại cùng một thời điểm trong ngày hay không.

Hai tấm ảnh có thể được chụp tại cùng một thời điểm nếu xoay được đồng hồ trong ảnh thứ ~2~ sao cho giống hệt với đồng hồ trong ảnh đầu tiên.

Công việc này sẽ là cơ hội vô cùng đáng giá đối với Phúc, nhất là với mức thu nhập hậu hĩnh từ chính phủ. Do đó, các bạn hãy giúp Phúc vượt qua kỳ sát hạch để có tiền uống cà phê khởi đầu sự nghiệp, xây dựng tương lai hạnh phúc của mình nhé!

Input

Dòng đầu tiên gồm ~1~ số nguyên dương ~n~ ~(2 \le n \le 2 \cdot 10^5)~ - số lượng kim chỉ thời gian của chiếc đồng hồ phép thuật.

~2~ dòng tiếp theo, mỗi dòng gồm ~n~ số nguyên dương ~a_1, a_2,...,a_n~ (~0\le a_i <360000~, ~\forall i \in [1;n])~, trong đó ~a_i~ là góc hợp bởi kim thứ ~i~ của đồng hồ so với phương thẳng đứng trên mỗi hình ảnh (theo chiều kim đồng hồ) được đo bằng đơn vị phần nghìn của ~1~ độ.

Biết rằng các kim đồng hồ khi được chụp ở cả hai thời điểm đều không trùng nhau, và kim đồng hồ khi quay một vòng sẽ đi được ~360~ độ.

Output

Gồm ~1~ dòng duy nhất - in ra YES nếu hai bức ảnh có thể là ảnh của cùng một thời điểm, và in NO trong trường hợp ngược lại.

Sample Input 1

6
1 2 3 4 5 6
7 6 5 4 3 1

Sample Output 1

NO

Sample Input 2

2
0 270000
180000 270000

Sample Output 2

YES

Sample Input 3

7
140 130 110 120 125 100 105
235 205 215 220 225 200 240

Sample Output 3

NO

Cho 1 hàng rào gồm ~n~ tấm ván xếp cạnh nhau, tấm ván thứ i có độ cao ~a_i~. Một decal trang trí có dạng 1 dãy các miếng dán dài ~m~, miếng thứ ~i~ có độ cao ~b_i~.

Một decal được dán hợp lệ trên 1 đoạn liên tiếp các tấm ván nếu: - Mọi ô của decal đều phủ lên ~1~ ô của tấm ván. - Với mỗi ô không được phủ bởi decal, ô bên dưới nó cũng không được phủ.

Đếm số cách hợp lệ để dán ~\geq 1~ decal lên hàng rào, sao cho không có ~2~ miếng dán nào đè lên nhau. Đáp án in ra mod ~10^9+7~.

Input

Dòng đầu tiên chứa 2 số ~n, m~ (~n, m \leq 250,000~) - độ dài của hàng rào và độ dài của miếng dán. Dòng thứ 2 chứa ~n~ số ~a_i~ (~a_i \leq 1,000,000~) - chiều cao của các đoạn hàng rào. Dòng cuối cùng chứa ~m~ số ~b_i~ (~b_i \leq 1,000,000~) - chiều cao của các đoạn decal.

Output

Một số nguyên trên một dòng duy nhất - đáp án của bài toán.

Sample Input 1

20 7
4 5 6 4 5 7 6 4 5 7 5 3 4 2 3 5 4 2 3 8 
2 3 1 2 4 3 1

Sample Output 1

3

Notes

Giải thích:

Trong test đầu tiên, decal có thể được dán ở vị trí 2, 12 hoặc là cả hai.

Cho 1 bảng ký tự và 1 xâu, người chơi sẽ xuất phát từ ô (~1~, ~1~) trên bảng kí tự và di chuyển đến ô (~n~, ~m~), chỉ được đi xuống hoặc đi qua phải.

Yêu cầu: Đếm số đường đi xuất hiện xâu đã cho.

Input

Dòng đầu tiên gồm 1 số duy nhất, ~t~ (~t \leq 10^6~) là số lượng test.

Sau đây là mô tả từng test.

• Dòng đầu tiên của test chứa hai số ~n~, ~m~ (~n \le 10^6~, ~m \le 10^6~) và một xâu ~s~ (~|s| \le 10^6~). Tích ~nm|s| \leq 10^6~.

• ~n~ dòng tiếp theo, mỗi dòng chứa 1 xâu gồm ~m~ kí tự.

• Lưu ý: Tất cả các xâu chỉ gồm các chữ cái in thường trong bảng chữ cái Latin, từ a đến z.

Tổng của ~nm|s|~ trong tất cả các test không vượt quá ~10^6~.

Output

In ra số đường đi xuất hiện xâu đã cho. Vì đáp án có thể rất lớn, hãy in ra đáp án modulo ~10^9 + 7~.

Sample Input 1

3
3 3
iwquemuoiwfuiwefmuiofmdsohmdjfhwieufhaiw
whw
ioe
qwe
5 5
cat
lurki
zzzzn
catzg
somew
herez
2 3
t
aaa
aaa

Sample Output 1

0
6
0

Cho 2 xâu ~s~, ~t~ ban đầu rỗng. Bạn cần xử lý ~Q~ query thuộc một trong 2 loại:

• ~1~ ~c~: thêm một chữ cái latin viết thường ~c~ vào cuối xâu ~s~

• ~2~ ~d~: thêm một chữ cái latin viết thường ~d~ vào cuối xâu ~t~

Sau mỗi query, tính giá trị biểu thức sau:

$$A(s, t) = \sum_{i=0}^{|t - 1|} cnt_i(s, t)*i$$

Trong đó ~cnt_i(s, t)~ là số lần xâu ~t_0t_1..t_i~ xuất hiện trong ~s~.

Input

Dòng đầu gồm một số nguyên dương ~Q~ ~(1 \leq Q \leq 3*10^5)~. ~Q~ dòng tiếp theo, mỗi dòng ghi một query gồm một số nguyên dương ~type~ ~(1 \leq type \leq 2)~ và một chữ cái latin viết thường.

Output

In ra ~Q~ dòng, dòng thứ ~i~ là giá trị của biểu thức ~A(s, t)~ sau query thứ ~i~.

Sample Input 1

8
1 a
2 a
1 a
2 a
1 a
2 a
1 a
1 a

Sample Output 1

0
0
0
1
2
4
7
10

Notes

Giải thích ví dụ 1:

• Query 1: ~s~ = ~a~, ~t~ rỗng. ~A(s, t) = 0~.

• Query 2: ~s~ = ~a~, ~t~ = ~a~. ~A(s, t) = cnt_0(s, t) * 0 = 0~.

• Query 3: ~s~ = ~aa~, ~t~ = ~a~. ~A(s, t) = cnt_0(s, t) * 0 = 0~.

• Query 4: ~s~ = ~aa~, ~t~ = ~aa~. ~A(s, t) = cnt_0(s, t) * 0 + cnt_1(s, t) * 1 = 0 + 1*1 = 1~.

• Query 5: ~s~ = ~aaa~, ~t~ = ~aa~. ~A(s, t) = cnt_0(s, t) * 0 + cnt_1(s, t) * 1 = 0 + 2*1 = 2~.

• Query 6: ~s~ = ~aaa~, ~t~ = ~aaa~. ~A(s, t) = cnt_0(s, t) * 0 + cnt_1(s, t) * 1 + cnt_2(s, t)*2 = 0 + 2*1 + 1*2 = 4~.

• Query 7: ~s~ = ~aaaa~, ~t~ = ~aaa~. ~A(s, t) = cnt_0(s, t) * 0 + cnt_1(s, t) * 1 + cnt_2(s, t)*2 = 0 + 3*1 + 2*2 = 7~.

• Query 8: ~s~ = ~aaaaa~, ~t~ = ~aaa~. ~A(s, t) = cnt_0(s, t) * 0 + cnt_1(s, t) * 1 + cnt_2(s, t)*2 = 0 + 4*1 + 3*2 = 10~.

Cho một xâu ~S~ có độ dài ~n \le 5*10^5~ gồm các chữ cái tiếng Anh in thường.

Một xâu tiền tố của xâu ~S~ được gọi là đẹp nếu nó bằng với xâu hậu tố tương ứng với nó. Hay nói cách khác, tiền tố độ dài ~L~ có dạng ~S[1,2,...,L]~ phải bằng với hậu tố độ dài ~L~ có dạng ~S[n-L+1,n-L+2,...,n]~.

Do việc tìm tất cả các xâu tiền tố đẹp là một công việc khá dễ dàng, nên Tí muốn giao thêm cho các bạn một công việc nữa, đó là với mỗi xâu tiền tố đẹp, hãy đếm xem có bao nhiêu xâu con liên tiếp trong ~S~ bằng với tiền tố đó.

Input

Dòng đầu gồm số nguyên dương ~n~ (~n \le 5*10^5~) miêu tả độ dài của xâu ~S~.

Dòng thứ hai miêu tả xâu ~S~.

Output

Dòng đầu tiên in ra số nguyên dương ~m~ là số lượng xâu tiền tố đẹp.

~m~ dòng sau, mỗi dòng in ra hai số nguyên dương ~u_i~ ~v_i~, với ~u_i~ là độ dài của xâu tiền tố đẹp tìm được, và ~v_i~ là số lần xuất hiện của nó.

Hãy in ra các cặp ~u_i~ ~v_i~ theo thứ tự tăng dần của ~u_i~.

Sample Input 1

7
abacaba

Sample Output 1

3
1 4
3 2
7 1

Sample Input 2

4
aaaa

Sample Output 2

4
1 4
2 3
3 2
4 1

Cho hai xâu ~X~ và ~Y~ chỉ gồm các kí tự in thường. Trong một thao tác, bạn có thể chọn một kí tự bất kì trên xâu ~X~ và xóa nó đi. Đếm số thao tác ít nhất để xâu ~Y~ không còn xuất hiện trong xâu ~X~ nữa.

Định nghĩa xâu ~A~ gọi là xuất hiện trong xâu ~B~ nếu tồn tại vị trí ~i~ (~1 \leq i \leq |B| - |A| + 1~) mà ~A_j = B_{i + j - 1} \forall j \in [1, |A|]~, ở đây mỗi kí tự được đánh chỉ số từ ~1~ từ trái qua phải và ~|t|~ là độ dài của xâu ~t~.

Input

Gồm ~3~ testcase, mỗi testcase trên hai dòng.

• Dòng đầu tiên chứa xâu ~X~ (~1\leq |X| \leq 10^4~).

• Dòng thứ hai chứa xâu ~Y~ (~1 \leq |Y| \leq 10^3~).

Output

Gồm ~3~ dòng, mỗi dòng in ra một số duy nhất là số thao tác ít nhất để xâu ~Y~ không còn xuất hiện trong xâu ~X~.

Sample Input 1

hhhhh
h
xywpywtddh
yw
cyapyaa
ya

Sample Output 1

5
2
2