DIFFSTR - Substrings

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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 < ...< x length(a) <= length(S) và a i = S Xi 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 <= 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)

Example 

Input:
2
bab
aa
cac
b
Output:
4
3
Giải thích: 
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"

Giới hạn

  • Trong tất cả các test n, m >= 1,
  • Xâu S, B chỉ gồm chữ thường từ 'a'..'z'
  • Trong 20% số test, n, m <= 20
  • Trong 40% số test tiếp theo, n, m <= 1.000 (10 3 )
  • Trong 40% số test tiếp theo, n, m <= 100.000 (10 5 )

  • Người up: songuku95
  • Nguồn bài: hgminh95