题目描述

如果一个线性同余方程 $a\cdot x \equiv 1 \pmod{b}$，则称 $x$ 为 $a \bmod b$ 的逆元，记作 $a^{-1}$。现在令 $b=10^9+7$，求 $a^{-1}$。

输入格式

输入一个 $a$，其中 $1 \leq a \leq 1000$。

输出格式

输出 $a^{-1}$。

输入输出样例

3

333333336

说明/提示

建议先学习逆元的知识。