Cho một bảng gồm H hàng và W cột ô lục giác đều. Các ô được đánh số bằng cặp tọa độ (r, c), với 1 ≤ r ≤ H và 1 ≤ c ≤ W. Hai ô được xem là kề cạnh nếu tọa độ của chúng là một trong các cặp sau (và cả hai ô đều thuộc bảng):

• (r, c) và (r, c + 1);
• Nếu r lẻ: (r, c) và (r + 1, c), hoặc (r + 1, c - 1);
• Nếu r chẵn: (r, c) và (r + 1, c), hoặc (r + 1, c + 1).

Có hai loại mảnh ghép:

• Mảnh loại 2 phủ đúng hai ô kề cạnh.
• Mảnh loại 3 phủ đúng ba ô, trong đó từng cặp ô đều kề cạnh (tạo thành một tam giác nhỏ).

Các mảnh có thể xoay tùy ý. Hãy đếm số cách lát kín bảng sao cho mỗi ô được phủ đúng một lần. Hai cách lát được xem là khác nhau nếu có ít nhất một ô thuộc các mảnh khác nhau.

Vì kết quả có thể rất lớn, hãy in kết quả modulo 1 000 000 007.

Dữ liệu vào

Một dòng gồm hai số nguyên H và W.

Dữ liệu ra

In ra số cách lát kín bảng modulo 1 000 000 007.

Ràng buộc

• 1 ≤ H ≤ 6
• 1 ≤ W ≤ 10^18

Phân nhóm điểm

1. (10 điểm) H = 1, W ≤ 10^5.
2. (20 điểm) H ≤ 2, W ≤ 10^5.
3. (30 điểm) H ≤ 4, W ≤ 10^18.
4. (40 điểm) H ≤ 6, W ≤ 10^18.

Ví dụ

Input

2 3

Output

4