Xét một hoán vị ~P=(p_1,p_2,\ldots,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~.

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 các số ~(1,2,\ldots,n)~ có đúng ~k~ phần tử cực đại. Kết quả được lấy theo modulo ~503~.

Input

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)~.

Output

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~.

Sample Input 1

3 1

Sample Output 1

4

Sample Input 2

3 2

Sample Output 2

2