Background

逆元求解的一个模板。

Description

给你一个数 $n（<10^7）$ ，求解 $\frac{1}{n}$ 在模 $10^9+7$ 的情况下的值。

Format

Input

输入一个数 $n$ 。

Output

输出$\frac{1}{n} \ mod \ 1000000007$。

Samples

5

400000003

Limitation