Cho số nguyên dương ~n~, hãy đếm số cặp nghiệm nguyên dương ~(x, y)~ của phương trình thỏa mãn:

$$ \frac{1}{x} + \frac{1}{y} = \frac{1}{n!} $$

Ký hiệu ~n! = 1 \times 2 \times 3 \times \ldots \times (n - 1) \times n~.

Dữ liệu

• Một dòng duy nhất chứa số nguyên dương ~n~ (~n \le 10^6~).

Kết quả

• Số cặp nghiệm nguyên dương ~(x, y)~ thỏa mãn đề bài chia dư cho ~20252026~.

Ví dụ

Input

2

Output

3

Giải thích: Với ~n = 2~ ta có 3 cặp nghiệm thỏa mãn là: ~(3, 6)~; ~(4, 4)~; ~(6, 3)~.

Giới hạn

• Subtask 1 (50% số điểm): ~n \le 10~;
• Subtask 2 (50% số điểm): Không có ràng buộc gì thêm.