Giải bài trực tuyến

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⁹ + 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₁< x₂< ...< 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⁹ + 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³)
• Trong 40% số test tiếp theo, n, m <= 100.000 (10⁵)