题目描述

我们知道，如果 $a×b=1$，即 $b=a^{-1}$, 那么 $b$ 是 $a$ 的倒数。

如果 $a×b=1(mod\ p)$，则 $b$ 就是在 $mod\ p$ 意义下的 $a$ 的倒数，我们称 $b$ 是 $a$ 在 $mod\ p$ 意义下的逆元。现在给你整数 $a$，你要求出其在 $mod\ 10^9+7$ 意义下的逆元。（即，求一个最小的正整数 $b$ ，满足 $a×b\%p=1$)。

输入格式

第一行一个整数 $T$ 表示测试数据的组数。$T$ 不超过 $10^5$。

接下来 $T$ 行每行一个正整数 $a$。$a$ 不超过 $10^9$。

输出格式

对每个 $a$，输出 $a$ 在 $mod\ 10^9+7$ 意义下的乘法逆元。

3
68
13
12345678

838235300
153846155
325842698

提示

$68×838235300=57000000400$

$13×153846155=2000000015$

$12345678×325842698=4022749028159244$

这三个数除以 $10^9+7$ 都余 $1$。