Cực đại của hoán vị

Xét một hoán vị $P=(p_1,p_2,\dots ,p_n)$ của các số nguyên từ $1$ đến $n$.

Phần tử $p_i$ ($1\le i\le n$) được gọi là một phần tử cực đại trong $P$ nếu $p_i>p_{i-1}$ và $p_i>p_{i+1}$, trong đó quy ước $p_0=p_{n+1}=0$. Như vậy $p_1$ là cực đại khi $p_1>p_2$, và $p_n$ là cực đại khi $p_n>p_{n-1}$; với $n=1$, phần tử duy nhất là cực đại.

Cho hai số nguyên dương $n$ và $k$.

Yêu cầu: Hãy xác định số lượng hoán vị của $(1,2,\dots ,n)$ có đúng $k$ phần tử cực đại. Kết quả được lấy theo modulo $503$.

Dữ liệu vào

Một dòng duy nhất gồm hai số nguyên $n$ và $k$ ($1\le n\le {10}^{15}$, $1\le k\le 30$).

Dữ liệu ra

In ra một số nguyên duy nhất là số lượng hoán vị có đúng $k$ phần tử cực đại, lấy theo modulo $503$.

Ràng buộc

• $1\le n\le {10}^{15}$.
• $1\le k\le 30$.

Ví dụ