该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

逆元求解的一个模板。

Description

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

Format

Input

输入一个数 $n$ 。

Output

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

Samples

5

400000003

Limitation