Đếm xâu theo mảng hậu tố

Cho một mảng hậu tố (suffix array) độ dài $n$ được xây dựng trên bảng chữ cái gồm $k$ ký tự. Nhiệm vụ của bạn là đếm xem có bao nhiêu xâu tạo ra đúng mảng hậu tố này.

Gọi $s$ là một xâu độ dài $n$ mà mỗi ký tự là một số nguyên trong tập $\{1,2,\dots ,k\}$ (ta so sánh các ký tự theo giá trị số). Hậu tố thứ $i$ của $s$ là xâu con $s[i\dots n-1]$ (chỉ số tính từ $0$). Mảng hậu tố của $s$ là dãy $s_0,s_1,\dots ,s_{n-1}$ gồm chỉ số bắt đầu của tất cả các hậu tố, sau khi các hậu tố được sắp xếp theo thứ tự từ điển tăng dần.

Ví dụ, mảng hậu tố của xâu oolimry là $[3,2,4,1,0,5,6]$, vì danh sách các hậu tố sau khi sắp xếp là $[\text{imry},\text{limry},\text{mry},\text{olimry},\text{oolimry},\text{ry},\text{y}]$.

Cho trước mảng hậu tố và kích thước bảng chữ cái $k$, hãy đếm số xâu độ dài $n$ trên bảng chữ cái $k$ ký tự tạo ra đúng mảng hậu tố đó. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho $998244353$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$: độ dài mảng hậu tố và kích thước bảng chữ cái.
• Dòng thứ hai chứa $n$ số nguyên $s_0,s_1,\dots ,s_{n-1}$ mô tả mảng hậu tố. Đảm bảo các $s_i$ đôi một khác nhau (là một hoán vị của $0,1,\dots ,n-1$).

Dữ liệu ra

• Một số nguyên duy nhất: số xâu tạo ra mảng hậu tố đã cho, lấy theo modulo $998244353$.

Ràng buộc

• $1\le n\le 200000$
• $1\le k\le 200000$
• $0\le s_i\le n-1$, các $s_i$ đôi một khác nhau.

Ví dụ