//Tuyên Quang 2014

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ượng trong bàn cờ vua nhưng luôn hướng sang bên phải.

Chẳng hạn: Như hình sau đây khi con rô bốt hiện tại đang ở ô có địa chỉ hàng 2, cột 1 thì bước đi tiếp theo của nó có thể đến được những ô có kí tự X.

Dữ liệu vào: Từ tệp ROBOT.INP chỉ gồm 2 số nguyên dương M và N (1  ≤ M, N  ≤ 3000).

Kết quả: Ghi vào tệp ROBOT.OUT gồm 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⁹.

Ví dụ:

Chú ý:

            - Có 30% test ứng với 30% số điểm với M, N ≤ 60.

            - Có 60% test ứng với 60% số điểm với M, N ≤ 300.