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≤i<K)\) gồm các kí tự thứ \(L_i\) đến kí tự thứ \(R_i\) của xâu \(S (1≤L_i≤R_i≤|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.

Dữ liệu: Vào từ thiết bị vào chuẩn (bàn phím) có khuôn dạng:

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

• Dòng thứ hai chứa xâu \(S\) chỉ gồm các kí tự \('a'\) đến \('z' (2^K×|S|≤2×10^5);\)

• Dòng thứ \(i (1≤i≤K-1)\) trong \(K-1\) dòng tiếp theo chứa hai số nguyên dương \(L_i,R_i (1≤L_i≤R_i≤|S|).\)

Kết quả: Ghi ra thiết bị ra chuẩn (màn hình) một dòng

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

Sample Input

1 1
abab

Sample Output

4

Sample Input

2 2
abab
2 3
## Sample Output

2 ```

Ràng buộc

• Subtask 1 (20 điểm): \(K=1;|S|≤2000;\)

• Subtask 2 (20 điểm): \(K=1;\)

• Subtask 3 (20 điểm): \(K≤7;|S|≤2000;\)

• Subtask 4 (20 điểm): \(K≤7.\)

• Subtask 5 (20 điểm): \(K=14.\)