Tại một buổi tiệc nọ, có \(n\) chàng hoàng tử và \(n\) nàng công chúa. Họ đã chuẩn bị một số món quà để tặng cho nhau. Tuy nhiên, một vấn đề nhỏ nảy sinh: nếu mọi người tặng quà lẫn nhau thì sẽ tốn rất nhiều thời gian. Vì vậy người tổ chức ami nghĩ ra một kế hoạch:

• Mỗi người chỉ tặng quà cho người khác giới. Tức là hoàng tử chỉ tặng quà cho các nàng công chúa, và công chúa chỉ tặng quà cho các chàng hoàng tử.
• Các cặp đôi sẽ trao đổi quà với nhau. Nghĩa là nếu hoàng tử A tặng quà cho công chúa B thì công chúa B cũng sẽ tặng lại cho A.
• Với mỗi cặp đôi, ami sẽ nhờ máy tính quyết định xem họ có trao đổi quà cho nhau không. Bằng kiến thức tin học đỉnh cao của mình, ami đã tạo ra một chương trình nói "Tặng" với xác suất \(\dfrac{1}{k}\) hoặc nói "Không tặng". Tất nhiên, bí kíp lập trình này ami không thể tiết lộ với các bạn.

ami không muốn các vị khách phải buồn, anh muốn rằng mọi người đến đây đều có quà mang về. Vì vậy trước khi quyết định, ami muốn nhờ các bạn tư vấn: Nếu thực hiện theo kế hoạch trên, thì xác suất để mọi người đều có quà là bao nhiêu?

Input

• Gồm một dòng chứa hai số nguyên dương \(n\) và \(k\).

Output

• Gọi \(p\) là xác suất các bạn tính được. Bằng kiến thức toán đỉnh cao của mình, ami đã chứng minh được rằng \(p \times k^{n^2}\) luôn là số nguyên (chứng minh chi tiết nhường lại cho các bạn). Vì vậy ami muốn các bạn hãy in ra một số là số dư của phép tính \(p \times k^{n^2}\) chia cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1\leq n \leq 4\) và \(k=2\);
• Subtask \(2\) (\(30\%\) số điểm): \(1\leq n \leq 300\) và \(2 \leq k \leq 10^9\);
• Subtask \(3\) (\(30\%\) số điểm): \(1\leq n \leq 3000\) và \(2 \leq k \leq 10^9\);
• Subtask \(4\) (\(20\%\) số điểm): \(1\leq n \leq 300,000\) và \(2 \leq k \leq 10^9\);

Example

2 2 

7

100 100 

828467084