Tạm gác hết những âu lo lại :v cùng mình giải bài toán này nhé. Mình cho các bạn một xâu kí tự \(s\) gồm \(n\) chữ cái in thường và một số nguyên \(k\). Bạn hãy giúp mình đếm số xâu kí tự \(t\) độ dài \(n\) cũng chỉ gồm các chữ cái in thường thỏa mãn điều kiện sau đây: Có chính xác \(k\) cặp số nguyên \((l, r)\) với \(1 \leq l \leq r \leq n\) và xâu con liên tiếp của \(t\) từ vị trí \(l\) đến vị trí \(r\) có thứ tự từ điển lớn hơn xâu con liên tiếp của \(s\) từ vị trí \(l\) đến vị trí \(r\).

Nhắc lại, xâu \(a = a_1 a_2 \ldots a_n\) được gọi là có thứ tự từ điển lớn hơn xâu \(b = b_1 b_2 \ldots b_n\) khi và chỉ khi tồn tại chỉ số \(i\) sao cho:

• \(1 \leq i \leq n\)
• \(a_i > b_i\)
• Với mọi chỉ số \(j\) sao cho \(1 \leq j < i\), ta luôn có \(a_j = b_j\).

Ví dụ, "tranchau" có thứ tự từ điển lớn hơn "tocotoco", "anhhanh" có thứ tự từ điển lớn hơn "anhanhh", "nguvanloi" có thứ tự từ điển lớn hơn "bichphuong", "thilin" có thứ tự từ điển lớn hơn "thaozi", "ntha" có thứ tự từ điển lớn hơn "dxmh".

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \((1 \leq n \leq 2000, 0 \leq k \leq 3000)\).
  Dòng thứ hai chứa xâu kí tự \(s\) gồm \(n\) chữ cái in thường.

Output

• In ra một số nguyên duy nhất là số xâu kí tự \(t\) thỏa mãn điều kiện trên. Do kết quả có thể rất lớn, bạn chỉ cần in ra đáp số theo modulo \(998244353\).

Scoring

Bộ test của bài được chia làm các subtask như sau:

• Subtask \(1\) (\(8\) điểm): \(n \leq 5\)
• Subtask \(2\) (\(8\) điểm): \(n \leq 10\)
• Subtask \(3\) (\(10\) điểm): \(n \leq 200\) và \(k \leq 300\)
• Subtask \(4\) (\(6\) điểm): \(k = 0\)
• Subtask \(5\) (\(12\) điểm): Xâu \(s\) chỉ gồm kí tự \(a\).
• Subtask \(6\) (\(16\) điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là \(60\) điểm.

Example

2 2
yy

26

2 3
yy

1