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 ~K - 1~ đoạn, đoạn thứ ~i~ (~1 \le i < K~) gồm các kí tự từ thứ ~L_i~ đến kí tự thứ ~R_i~ của xâu ~S~ (~1 \le L_i \le R_i \le |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 \le |S|~);
• Dòng thứ hai chứa xâu ~S~ chỉ gồm các kí tự ~'a'~ đến ~'z'~ (~2^K \times |S| \le 2 \times 10^5~);
• Dòng thứ ~i~ (~1 \le i \le K - 1~) trong ~K - 1~ dòng tiếp theo chứa hai số nguyên dương ~L_i, R_i~ (~1 \le L_i \le R_i \le |S|~).

Output

Số lượng cách chọn đoạn thỏa mãn.

Sample Input 1

1 1
abab

Sample Output 1

4

Sample Input 2

2 2
abab
2 3

Sample Output 2

2

Subtasks

• Subtask 1 (20 điểm): ~K = 1; |S| \le 2000~;
• Subtask 2 (20 điểm): ~K = 1~;
• Subtask 3 (20 điểm): ~K \le 7; |S| \le 2000~;
• Subtask 4 (20 điểm): ~K \le 7~;
• Subtask 5 (20 điểm): ~K = 14~.