.Cho 1 dãy gồm n phần tử, phần tử 1 và n đã được xác định. Hỏi có bao nhiêu cách điền các số từ 1 đến k vào vị trí từ 2 đến n-1 sao cho không có 2 số cạnh nhau bằng nhau? Vì số cách rất lớn, nên in ra phần dư của kết quả cho 998244353.
Input: Dòng đầu chứa 2 số n và k. (n <= 10^6, k <= 10^6).
Dòng thứ 2 chứa 2 số tương ứng là a[1] và a[n].
Ouput: Đáp án của đề bài.
Example:
|
input |
output |
|
3 10 1 1 |
9. |
*có 9 cách là điền các số từ 2 đến10 vào vị trí 2.
*50% số test có n*k <= 10^7.