Trong truyền thuyết của CLB H3.2 viết, những con cá hồi có thể vượt qua nhiều vũ môn để trở thành InfinitySalmon. Mỗi vũ môn là một chặng đường phấn đấu trong cuộc đời của con cá hồi và được đại diện bởi một con số nguyên dương. Như vậy các vũ môn sẽ tạo thành một dãy gồm ~n~ số nguyên dương tăng ngặt và vũ môn cuối cùng có giá trị không vượt quá ~m~. Con cá hồi trong câu chuyện hôm nay khá đặc biệt, nó thích trong lần thứ ~i~ (với ~1 \le i \le n~) thì giá trị vũ môn nó vượt qua sẽ có cùng số dư với ~i^2~ khi chia cho ~k~. Bạn hãy giúp con cá hồi đếm xem có bao nhiêu cách để trở thành InfinitySalmon nhé, do kết quả có thể rất lớn nên lấy modulo ~10^9+7.~

Input

Một dòng duy nhất gồm ba số nguyên dương ~n,m,k~ trong đó ~1 \le n \le 10^5~, ~1 \le m \le 10^9~, ~1 \le k \le 10^6~.

Output

Đáp số của bài toán.

Sample input 1.

2 4 2

Sample output 1.

3

Sample input 2.

12 2021 12

Sample output 2.

608212426

Giải thích. Trong VD1, con cá hồi có thể nhảy với các cách là: ~1 \to 2~ hoặc ~1 \to 4~ hoặc ~3 \to 4~.