Trong kì thi đại học môn Toán, Khôi gặp câu trắc nghiệm như sau:

\(50.\) Đếm có bao nhiêu dãy số có \(5\) phần tử có các giá trị phần tử từ \(1\) đến \(10\) sao cho tổng của chúng là số chẵn.

A. 1000          B. 300          C. 5000          D. 350

Vì chỉ còn \(5s\) nữa là hết giờ làm bài nên Khôi quyết định chọn luôn \(C\).

Và sau khi biết được kết quả thì câu đó \(C\) là đáp án chính xác @@.

Sau khi biết được đáp án của mình chính xác, Khôi rất vui mừng và cố gắng giải quyết bài toán \(1\) cách tổng quát.

Tổng quát: Đếm có bao nhiêu dãy số có \(n\) phần tử. Mỗi phần tử nhận giá trị từ \(1\) đến \(m\) sao cho tổng của chúng là số chẵn.

Nhưng sau một hồi suy nghĩ, Khôi vẫn chưa nghĩ ra được công thức, hãy giúp Khôi giải bài toán này nhé.

Lưu ý: vì kết quả có thể rất lớn nên chỉ cần lấy phần dư của kết quả cho \(10^9+7\).

Input

• Một dòng duy nhất gồm hai số nguyên \(n\) và \(m\) \((1 \leq n, m \leq 10^{18})\).

Output

• In ra một số duy nhất là số dãy số thỏa mãn yêu cầu, lấy phần dư cho \(10^9+7\).

Example

2 3

5

5 10

50000