Alice muốn đặt mật khẩu cho một ứng dụng mà cô mới xây dựng. Cô đã chọn xâu kí tự \(S\) (kí hiệu \(|S|\) là độ dài xâu \(S\)) và dự định chọn \(K\) đoạn trên xâu \(S\) (các đoạn gồm ít nhất một kí tự và không nhất thiết rời nhau) rồi ghép các đoạn theo một thứ tự nào đó để nhận được xâu đối xứng. Nhắc lại, xâu đối xứng là xâu đọc từ trái qua phải cũng như đọc từ phải qua trái, ví dụ abba, sos là xâu đối xứng, còn xâu abab thì không phải là xâu đối xứng. Alice đã chọn đoạn \(K - 1\), đoạn thứ \(i\) \((1 \leq i < K)\) gồm các kí tự thứ \(L_{i}\) đến kí tự thứ \(R_{i}\) của xâu \(S\) \((1 \leq L_{i} \leq R_{i} \leq |S|)\). Khi chọn đoạn thứ \(K\), Alice muốn chọn một đoạn có độ dài \(m\) mà với đoạn đó Alice có thể ghép với \(K - 1\) đoạn đã chọn theo một thứ tự nào đó để nhận được một xâu đối xứng.

Yêu cầu: Cho xâu \(S\) và \(K - 1\) cặp số \(L_{i}, R_{i}\), hãy đếm số cách chọn đoạn thỏa mãn.

Input

Dòng đầu chứa hai số nguyên dương \(K, m\) \((m \leq S)\);

• Dòng thứ hai chứa xâu \(S\) chỉ gồm các kí tự a đến z \((2^{K} \times |S| \leq 2 \times 10^{5})\);
• Dòng thứ \(i\) \((1 \leq i \leq K - 1)\) trong dòng tiếp theo chứa hai số nguyên dương \(L_{i}, R_{i}\) \((1 \leq L_{i} \leq R_{i} \leq |S|)\).

Output

• Ghi ra một dòng chứa một số là số lượng cách chọn thỏa mãn.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(K = 1, |S| \leq 2000\).
• Subtask \(2\) (\(20\%\) số điểm): \(K = 1\).
• Subtask \(3\) (\(20\%\) số điểm): \(K \leq 7, |S| \leq 2000\).
• Subtask \(4\) (\(20\%\) số điểm): \(K \leq 7\)
• Subtask \(5\) (\(20\%\) số điểm): \(K = 14\).

Example

1 1
abab

4

2 2
abab
2 3

2