Substrings

View as PDF

Submit solution

Points: 1.36 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
hgminh95
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

hgminh là một thành viên mới của tập đoàn trách nhiệm hữu hạn nhiều thành viên phi lợi nhuận đào tạo coder: Cờ Một Một.

Không may thay, khi vừa vào anh bị tổ trưởng điểm danh Cà Dốt chơi khó, anh cần tìm số thứ tự trong danh sách nhân viên. Cà Dốt cho anh một xâu ~S~ độ dài ~n~, tên của hgminh trong danh sách là xâu ~B~ độ dài ~m~. Để tìm ra số thứ tự của mình, hgminh cần phải đếm số xâu con (định nghĩa xâu con xem ở dưới) phân biệt của xâu ~S~ thỏa mãn:

  • ~2~ ký tự kề nhau trong xâu con phải khác nhau
  • Có thứ tự từ điển không nhỏ hơn xâu ~B~

Vì kết quả rất to mà hgminh chưa học số lớn nên Cà Dốt quyết định sẽ yêu cầu hgminh đưa ra kết quả sau khi mod ~1000000007~ ~(10^{9} + 7)~

Xâu ~a~ gọi là xâu con của ~S~ nếu tồn tại ~1~ dãy ~x~ thỏa mãn ~0 < x_{1} < x_{2} < \dots < x_{length(a)} \le length(S)~ và ~a_{i} = S_{X_i}~ với mọi ~i~ từ ~1~ đến ~length(a)~.

Ví dụ xâu "aba" có ~6~ xâu con phân biệt khác rỗng là: "a", "b", "ab", "ba", "aa", "aba"

Input

  • Dòng ~1~: số nguyên dương ~t~ là số test ~(t \le 5)~

  • Mỗi test có định dạng như sau:

    • Dòng ~1~: xâu ~S~ độ dài ~n~
    • Dòng ~2~: xâu ~B~ độ dài ~m~

Output

  • Gồm ~t~ dòng, dòng thứ ~i~ là kết quả của test thứ ~i~ sau khi mod ~1000000007~ ~(10^{9} + 7)~

Giới hạn

  • Trong tất cả các test ~n~, ~m \geq 1~,
  • Xâu ~S~, ~B~ chỉ gồm chữ thường từ 'a' ...'z'
  • Trong ~20\%~ số test, ~n~, ~m \le 20~
  • Trong ~40\%~ số test tiếp theo, ~n~, ~m \le 1\,000 (10^{3})~
  • Trong ~40\%~ số test tiếp theo, ~n~, ~m \le 100\,000 (10^{5})~

Sample Input

2
bab
aa
cac
b

Sample Output

4
3

Note

Xâu "bab" có 4 xâu con thỏa mãn là: "b", "ab", "ba", "bab"

Xâu "cac" có 3 xâu con thỏa mãn là: "c", "ca", "cac"


Comments

Please read the guidelines before commenting.


There are no comments at the moment.