Cho 2 số nguyên dương ~m~ , ~n~ . Nhiệm vụ của bạn là phải đếm xem có bao nhiêu dãy ~a_1,a_2,...,a_{n}~ thỏa mãn các điều kiện sau:

• ~ 1\le a_{i} \le m ~ với mọi ~ 1\le i \le n ~.
• Tổng của tất cả các số trong dãy chia hết cho ~ m ~ .

Vì kết quả có thể rất lớn nên ta chỉ lấy phần dư của kết quả khi chia cho ~ k ~ ( ~ k ~ được nhập từ đầu vào).

Input

Gồm 3 dòng theo thứ tự mỗi dòng là:

• Dòng đầu là giá trị của m ( ~ 1\le m \le 10^{100000} ~ ).
• Dòng thứ hai là giá trị của n ( ~ 1\le n \le 10^{100000} ~ ).
• Dòng thứ 3 là giá trị của k ( ~ 1 \le k \le 10^{9} ~ ).

Output

In ra kết quả theo yêu cầu bài toán.

Sample

Input #1

7
2
5

Output #1

2