Cho một dãy số ~a_{1}~ ...~a_{N}~ là một hoán vị các số tự nhiên từ ~1~ đến ~N~. Hoán vị này gọi là đẹp nếu trị tuyệt đối ~|a_{i} - i| \le M~ với mọi ~i~ từ ~1~ đến ~N~ và ~M~ cho trước. Nhiệm vụ của bạn là đếm số hoán vị đẹp.

Input

Gồm nhiều dòng, mỗi dòng ghi ~2~ số ~N~, ~M~ ~(1 \le N \le 100~, ~1 \le M \le 6)~.

Output

Mỗi dòng tương ứng từng bộ test là số dư của số hoán vị đẹp cần tìm chia cho ~10^{9}~.

Sample Input

3 1
3 2

Sample Output

3
6