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~.

Subtasks

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

• Subtask ~1~ (~7~ test): ~n \leq 5~
• Subtask ~2~ (~6~ test): ~n \leq 10~
• Subtask ~3~ (~8~ test): ~n \leq 200~ và ~k \leq 300~
• Subtask ~4~ (~5~ test): ~k = 0~
• Subtask ~5~ (~10~ điểm): Xâu ~s~ chỉ gồm kí tự ~a~.
• Subtask ~6~ (~12~ đ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.

Ví dụ

Input 1

2 2
yy

Output 1

26

Input 2

2 3
yy

Output 2

1

Giải thích

Trong ví dụ thứ nhất, ta có xâu ~s~ là "yy". Khi đó, xâu ~t~ là "za" thỏa mãn vì:

• Với ~l = 1~ và ~r = 1~, ta có "z" > "y".
• Với ~l = 2~ và ~r = 2~, ta có "a" < "y".
• Với ~l = 1~ và ~r = 2~, ta có "za" > "yy".

Như vậy, có chính xác ~k = 2~ cặp chỉ số ~(l, r)~ để xâu con liên tiếp từ ~l~ đến ~r~ ở ~t~ có thứ tự từ điển lớn hơn xâu con liên tiếp từ ~l~ đến ~r~ ở ~s~.

Tương tự, xâu "yz" cũng thỏa mãn vì:

• Với ~l = 1~ và ~r = 1~, ta có "y" = "y".
• Với ~l = 2~ và ~r = 2~, ta có "z" > "y".
• Với ~l = 1~ và ~r = 2~, ta có "yz" > "yy".

Như vậy, có chính xác ~k = 2~ cặp chỉ số ~(l, r)~ để xâu con liên tiếp từ ~l~ đến ~r~ ở ~t~ có thứ tự từ điển lớn hơn xâu con liên tiếp từ ~l~ đến ~r~ ở ~s~.

Ngược lại, xâu "az" không thỏa mãn vì:

• Với ~l = 1~ và ~r = 1~, ta có "a" < "y".
• Vơi ~l = 2~ và ~r = 2~, ta có "z" > "y".
• Với ~l = 1~ và ~r = 2~, ta có "az" < "yy".

Như vậy, chỉ có ~1~ cặp chỉ số ~(l, r)~ để xâu con liên tiếp từ ~l~ đến ~r~ ở ~t~ có thứ tự từ điển lớn hơn xâu con liên tiếp từ ~l~ đến ~r~ ở ~s~.

Tương tự, xâu "zz" cũng không thỏa mãn vì:

• Với ~l = 1~ và ~r = 1~, ta có "z" > "y".
• Vơi ~l = 2~ và ~r = 2~, ta có "z" > "y".
• Với ~l = 1~ và ~r = 2~, ta có "zz" > "yy".

Như vậy, có tới ~3~ cặp chỉ số ~(l, r)~ để xâu con liên tiếp từ ~l~ đến ~r~ ở ~t~ có thứ tự từ điển lớn hơn xâu con liên tiếp từ ~l~ đến ~r~ ở ~s~.

~26~ xâu kí tự thỏa mãn điều kiện đề bài trong ví dụ thứ nhất là: "yz", "za", "zb",..., "zy".

Trong ví dụ thứ hai, "zz" là xâu duy nhất thỏa mãn điều kiện đề bài.