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ứa các 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 đó (lượt thứ lẻ rút từ hộp thứ nhất, lượt thứ chẵn rút từ hộp thứ hai).

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 giá trị các thẻ sau $n$ lần rút là một số chia hết cho $m$. Hai cách rút được coi là khác nhau nếu có một lượt mà giá trị thẻ rút được ở hai cách khác nhau.

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.

Dữ liệu vào

Một dòng gồm ba số nguyên dương $n,k,m$ $(2\le n,k\le {10}^9,m\le 100)$.

Dữ liệu ra

In ra một số nguyên 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 bạn chỉ cần đưa ra phần dư của đáp án khi chia cho $123456789$ (phần dư này có thể bằng $0$).

Ràng buộc

• $2\le n\le {10}^9$, $2\le k\le {10}^9$, $1\le m\le 100$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $n,k\le 1000$.
• Subtask 2 ($30\%$ số điểm): $m$ lẻ, $n\le {10}^3$.
• Subtask 3 ($30\%$ số điểm): $n\le {10}^3$.
• Subtask 4 ($20\%$ số điểm): Không có ràng buộc gì thêm.

Ví dụ