Background

It is the season when cherry blossoms bloom again. When Vani and the girl went to see the cherry blossoms, they found a big cherry tree full of pink blossoms. Vani roughly estimated that there were $n!$ petals.

Vani gently said to her: "Do you know? One petal among them represents you. If I randomly pick one, the probability that I meet you is only $1/n!$. How lucky I must be to have you standing so close in front of me today. Believe me, I will turn this one-in-hundreds-of-millions fate into forever."

Pink cherry blossoms fluttered all over the sky, and the girl was instantly touched by Vani. She gently held his hand, and they sat close together. At this moment, she suddenly saw two cherry trees at the end of the field, then slowly leaned her head on Vani’s shoulder and whispered in his ear: "Do you see those two cherry trees in the sunset? One petal on one tree is you, and one petal on the other tree is me. If someone picks one petal from this tree and one from that tree, will the probability that we meet happen to be $1/n!$?"

Vani’s brain ran fast, and he immediately got the answer. Just as he was about to tell the girl, she softly said again: "You used to say I’m bad at math, but I can still do this simple problem. Look, if the tree on the left has $x$ petals and the one on the right has $y$ petals, then the probability that we meet is just $1/x + 1/y$, but how many cases make it exactly equal to $1/n!$? Please help me figure this out~"

Obviously, facing the adorably airheaded girl, Vani not only cannot complain about her math, but also has to honestly compute the answer for her.

Problem Description

Find the number of ordered positive integer solutions to the equation:

Output the answer modulo $10^9+7$.

Input Format

The input consists of a single integer $n$.

Output Format

Output a single integer: the number of ordered positive integer pairs $(x, y)$ modulo $10^9+7$.

2

3

1439

102426508

Hint

Sample 1 Explanation

There are three pairs $(x, y)$ that satisfy the condition: $(3,6)$, $(4,4)$, and $(6,3)$.

Constraints

• For $30\%$ of the testdata, it is guaranteed that $n \le 100$.
• For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 10^6$.

Translated by ChatGPT 5