weights

Bạn có n quả cân. Một quả cân nặng 1kg, một quả cân nặng 2kg, …, một quả cân nặng nkg. Ngoài ra, bạn cũng có một quả cân khác mkg.

Nhiệm vụ của bạn là tính toán số cách để cân bằng các quả cân này trên một cái cân 2 đĩa, với một quả cân đặc biệt (mkg) được đặt trên đĩa bên trái. Không cần sử dụng tất cả quả cân kia, nhưng phải sử dụng quả cân mkg.

Kết qủa có thể khá lớn, trả về phần dư của kết quả cho 10⁹ + 9.

Ví dụ

Với n = 4 và m = 2, đầu ra là weights(n, m) = 7.

Các cách để cân cân bằng:

Đầu vào/Đầu ra:

[giới hạn thời gian chạy] 0.5 seconds
[đầu vào] integer n

Số các quả cân: 1 quả 1 kg, 1 quả 2 kg,…, 1 quả nkg.

1 ≤ n ≤ 30.

[đầu vào] integer m

Khối lượng quả cân đặc biệt mkg.
1 ≤ m ≤ 100.
[đầu ra] long
Phần dư trong phép chia của số cách có thể đạt được cho 10⁹ + 9.