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 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 đó.

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

Ba số nguyên dương ~n, k, m~ ~(2 \le n, k \le 10^9, m \le 100)~.

Output

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 bạn chỉ cần đưa ra phần dư của đáp án khi chia cho ~123456789~.

Scoring

Sample Input 1

3 4 4

Sample Output 1

4

Sample Input 2

3 2 4

Sample Output 2

1

Notes

Giải thích test ví dụ 1:

Có tất cả ~8~ cách rút tất cả nhưng có ~4~ cách rút thẻ có tổng chia hết cho ~4~

• Cách 1: 1 2 1
• Cách 2: 1 4 3
• Cách 3: 3 4 1
• Cách 4: 3 2 3