Bài tập

\begincenter

\endcenter

\begincenter

\endcenter

Example

5 2
3 1 2 3
2 2 4

34

Bạn được cho một bảng số gồm \(n\) hàng và \(m\) cột. Trong mỗi ô của bảng, bạn được điền một con số từ \(1\) đến \(k\). Tuy nhiên có ràng buộc đặc biệt là trong mỗi hàng và mỗi cột của bảng thì phải chứa ít nhất \(1\) ô được điền số \(1\).

Nhiệm vụ của bạn là đếm số cách điền bảng trên sao cho thỏa mãn ràng buộc.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, k\) \((1 \leq n, m \leq 1000, 1 \leq k \leq 10^9)\), lần lượt là số hàng, số cột và số con số có thể sử dụng để điền vào bảng.

Output

In ra số cách điền bảng trên. Vì kết quả có thể rất lớn, in ra đáp án khi chia dư cho \(10^9 + 7\).

Example

2 2 3

17

3 4 3

101089

Scoring

• Có \(20\%\) số điểm ứng với \(n \times m \le 20\).
• Có \(30\%\) số điểm ứng với \(n, m \le 500\).
• Có \(50\%\) số điểm ứng với \(n, m \le 1000\).

Bờm tham gia trò chơi rút thăm trúng thưởng trong đêm hội Trăng rằm. Ban tổ chức chuẩn bị \(k\) loại thẻ bài, các loại thẻ bài tương ứng ghi các giá trị từ \(1\) đến \(k\), các thẻ được sắp xếp vào trong \(2\) chiếc hộp như sau:

• Hộp thứ nhất: chỉ chứa các loại thẻ bài có giá trị là số lẻ trong khoảng từ \(1\) tới \(k\), số lượng mỗi loại thẻ không giới hạn.
• Hộp thứ hai: chỉ chứa các loại thẻ bài có giá trị là số chẵn trong khoảng từ \(1\) tới \(k\), số lượng mỗi loại thẻ không giới hạn.

Theo thể lệ của Ban tổ chức, một người chơi sẽ được thực hiện \(n\) lần rút thẻ. Các lượt rút thẻ theo thứ tự bắt đầu từ hộp thứ nhất tới hộp thứ hai và lặp lại quá trình đó.

Ví dụ: \(k = 4, n = 3\)

• Lượt thứ nhất: Người chơi rút thẻ trong hộp thứ nhất có thể nhận được các thẻ bài có giá trị \(1\) hoặc \(3\).
• Lượt thứ hai: Người chơi rút thẻ trong hộp thứ hai có thể nhận được các thẻ bài có giá trị \(2\) hoặc \(4\).
• Lượt thứ ba: Người chơi rút thẻ trong hộp thứ nhất có thể nhận được các thẻ bài có giá trị \(1\) hoặc \(3\).

Ban tổ chức đưa ra một con số \(m\) và người chơi sẽ nhận được quà nếu tổng số thẻ sau \(n\) lần rút là một số chia hết cho \(m\).

Yêu cầu: Hãy tính giúp Bờm xem có bao nhiêu cách rút ra các thẻ bài để có thể nhận được thưởng.

Input

Một dòng chứa ba số nguyên dương \(n, k, m\) \((2 \le n, k \le 10^9, m \le 100)\).

Output

Ghi ra một số nguyên dương là số cách rút thẻ thỏa mãn yêu cầu của Ban tổ chức. Vì kết quả rất lớn nên chỉ cần đưa ra phần dư của đáp án khi chia cho \(123456789\).

Example

3 4 4

4

3 2 4

1

Scoring

• Subtask 1 (20%): \(n, k \leq 1000\).
• Subtask 2 (30%): \(m\) lẻ, \(n \leq 10^3\).
• Subtask 3 (30%): \(n \leq 10^3\).
• Subtask 4 (20%): Không có ràng buộc gì thêm.