Đếm chuỗi

Cho chuỗi \(T\) độ dài \(n\) được nén theo kỹ thuật RLE (Run Length Encoding). Chuỗi nén này gồm các cặp ký tự và số nguyên dương, biểu diễn số lần lặp liên tiếp của ký tự đó.

Ví dụ: chuỗi nén \(\texttt{a3b2c1}\) tương ứng với chuỗi gốc \(T = \texttt{aaabbc}\).

Bạn được cho một chuỗi con \(P\), và một dãy \(a_1, a_2, \ldots, a_m\) gồm \(m\) vị trí tăng dần (đánh số từ \(1\)), sao cho nếu ta lấy ký tự thứ \(a_i\) trong chuỗi \(T\) và ghép lại theo thứ tự, ta được chuỗi \(P\).

Gọi \(R\) là số lượng dãy \((a_1, a_2, \ldots, a_m)\) khác nhau thỏa mãn điều kiện trên. Hãy in ra \(R \; mod \; 10^9+7\).

Input

• Dòng đầu chứa hai số nguyên dương \(n, m\) (độ dài của xâu \(T\) trước khi nén và độ dài của một dãy cần tìm);
• Dòng thứ hai chứa một xâu là mã hóa của xâu \(T\); (mỗi kí tự được lặp liên tiếp không quá \(10^9\) lần).
• Dòng thứ ba chứa một xâu là xâu \(P\).

Output

• Ghi ra một số nguyên duy nhất là số \(R\) chia dư cho \(10^9 + 7\).

Example

9 5
m1i1s2y1o1u3
isyou

6

11 3
m1i1s2i1s2i1p2i1
isi

14

Scoring

• Subtask 1 (20% số điểm): \(n \leq 20\), \(m = 1\);
• Subtask 2 (20% số điểm): \(n \leq 20\), \(m < n\);
• Subtask 3 (20% số điểm): \(n \leq 10^5\), \(m = 3\);
• Subtask 4 (20% số điểm): \(n \leq 10^5\), \(m \leq 30\);
• Subtask 5 (20% số điểm): \(n \leq 10^9\), \(m \leq 30\) và xâu mã hóa của xâu \(T\) có độ dài không vượt quá \(10^5\).