Rút thăm trúng thưởng

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.