Petar và Ivana đang chán trong một buổi chiều mùa đông dài nên quyết định nghĩ ra một trò chơi với các con số.

Petar lấy một tờ giấy rồi ngẫu nhiên viết ra ~n~ số. Mỗi số được chọn độc lập và đồng xác suất trong tập các số nguyên từ ~1~ đến ~k~. Theo cách đó, Petar tạo ra một mảng ~a~ gồm ~n~ phần tử.

Ivana nói rằng cô đặc biệt thích một số mảng vì chúng có một “sự cân bằng ẩn”, và cô gọi những mảng đó là cấu trúc. Một mảng được gọi là cấu trúc nếu đồng thời thỏa mãn hai điều kiện sau:

• Mỗi số từ ~1~ đến ~n~ xuất hiện trong mảng đúng một lần.
• Với mọi chỉ số ~i~ thỏa ~1 \le i \le n~, ta có ~|a_i + i - n - 1| \le 1~.

Ivana muốn biết xác suất để Petar, khi chọn ngẫu nhiên hoàn toàn như mô tả ở trên, tạo ra được một mảng là cấu trúc.

Có thể chứng minh rằng đáp án luôn biểu diễn được dưới dạng phân số ~\frac{P}{Q}~, trong đó ~P~ là số nguyên còn ~Q~ là số nguyên dương không chia hết cho ~10^9 + 7~. Khi đó, bạn cần in ra giá trị ~P \cdot Q^{-1} \pmod{10^9 + 7}~.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~.

Output

In ra một số nguyên duy nhất là đáp án của bài toán.

Ràng buộc

• ~1 \le n, k \le 10^9~

Chấm điểm

• Subtask 1 (17 điểm): ~n, k \le 7~
• Subtask 2 (23 điểm): ~n \le 7~, ~k \le 100~
• Subtask 3 (19 điểm): ~n \le 20~, ~k \le 100~
• Subtask 4 (25 điểm): ~n, k \le 10^6~
• Subtask 5 (26 điểm): Không có ràng buộc bổ sung.

Sample Input 1

2 1

Sample Output 1

0

Sample Input 2

2 2

Sample Output 2

500000004

Sample Input 3

7 94

Sample Output 3

100976822

Giải thích

• Ví dụ 2: Petar có thể tạo ra ~4~ mảng: ~ (1, 1), (1, 2), (2, 1), (2, 2) ~. Trong số đó, các mảng là cấu trúc là ~ (1, 2) ~ và ~ (2, 1) ~. Vì vậy xác suất bằng ~\frac{2}{4}~, tức là ~500000004 \pmod{10^9 + 7}~.