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"