Зсув сиру#13002

Зсув сиру

2 seconds
1,024 megabytes
Very hard

Джеррі акуратно розклав шматочків сиру в ряд, причому всі вони мають різні розміри. Він вирішив виміряти, наскільки невпорядкованим є це розташування — для нього це означає порахувати всі пари шматочків сиру, у яких більший шматочок розташований раніше за менший. Джеррі нарахував рівно таких пар.

Джеррі часто жартує над Томом, але цього разу настала черга Тома помститися. Він узяв перші шматочків сиру та перемістив їх у кінець ряду, не змінюючи їхнього взаємного порядку. Після такого зсуву нове розташування містило рівно невпорядкованих пар.

Тепер Том хоче дізнатися, скільки різних початкових розташувань шматочків сиру могли мати рівно невпорядкованих пар до зсуву та рівно після нього.

Input

У першому рядку задано два цілі числа та .

У другому рядку задано два цілі числа та .

2 \le n \le 500,

1 \le k \le \min(n - 1, 20),

0 \le a, b \le \frac{n \cdot (n - 1)}{2}.

Output

Виведіть одне ціле число — кількість можливих початкових розташувань за модулем простого числа 998244353.

Examples

Example

Loading
Loading