Cho một bảng hình chữ nhật gồm ~M~ hàng và ~N~ cột, các hàng được đánh số từ ~1~ đến ~M~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~N~ từ trái sang phải.

Một con rô bốt có thể xuất phát từ một ô bất kỳ nào đó trên cột ~1~ và đi đến ~1~ ô bất kỳ trên cột ~N~. Tại mỗi bước đi con rô bốt có thể di chuyển theo nước đi của quân tịnh trong bàn cờ vua nhưng luôn hướng sang bên phải.

Yêu cầu: Hãy tính số cách mà con rô bốt có thể di chuyển từ cột ~1~ đến cột ~N~.

Input

• Chỉ gồm 2 số nguyên dương ~M~ và ~N~ (~1 \le M, N \le 3000~).

Output

• Ghi một số nguyên dương duy nhất là số cách di chuyển của rô bốt chia lấy phần dư cho ~10^9~.