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