Bài 3 của đề /ckfinder/userfiles/files/TEST2.pdf

Dãy (𝑎₁, 𝑎₂, . . . , 𝑎_𝑛) là một hoán vị của các số tự nhiên từ 1 đến 𝑛 được gọi là có 𝑘 cực trị nếu: 𝑎_𝑖−1 < 𝑎_𝑖 và 𝑎_𝑖 > 𝑎_𝑖+1 thực hiện với đúng 𝑘 giá trị 𝑖 khác nhau (coi 𝑎₀ = 𝑎_𝑛+1 = 0).

Ví dụ, hoán vị (3, 1, 4, 5, 2) có 2 cực trị với 𝑖 = 1 và 𝑖 = 4.

Yêu cầu: Cho 𝑛 và 𝑘. Gọi 𝑠 là số lượng hoán vị có đúng 𝑘 cực trị, tính 𝑠 𝑚𝑜𝑑 239.

Dữ liệu vào

Một dòng chứa 2 số nguyên 𝑛 và 𝑘 cách nhau một dấu cách (1 ≤ 𝑛 ≤ 10¹⁵ , 1 ≤ 𝑘 ≤ 30).

Kết quả

Một số nguyên là 𝑠 𝑚𝑜𝑑 239.