[湖北省队互测2014] 一个人的数论

题目来源：$2014$ 年湖北省队互测Week1 资源来源：[链接](https://tieba.baidu.com/p/3050650090?red_tag=3002680446)

有一天 hjy96 想到了一个数论问题: 对于一个非负整数 $d$ 和一个正整数 $n$，定义 $f_d(n)$ 为所有小于 $n$ 且与 $n$ 互质的正整数的 $d$ 次方之和。如 $f_3(10) = 1^3 +3^3 +7^3 +9^3$。 现给定 $d, n$，求 $f_d(n)$ 的值。输出答案对 $10^9 + 7$ 取模后的结果。 hjy96 当然知道怎么做啦! 但是他想考考你......

由于 $n$ 可能很大，我们给出 $n$ 的质因数分解式。 $$ n=\prod_{i=1}^{w} p_{i}^{\alpha_{i}} $$ 第一行有用空格隔开的一个非负整数 $d$, 一个正整数 $w$。 接下来 $w$ 行，每行有两个用空格隔开的正整数 $p_i$, $α_i$。(保证 $p_i$ 为素数且互不相同)

一行，一个非负整数表示 $f_d(n)$ 对 $10^9 + 7$ 取模后的结果。

3 2 
2 1 
5 1

1100

#### 数据规模与约定 各测试点信息如下表 | 编号 | $d$ | 特殊限制 | | :---: | :---: | :---------: | | 1 | $\leq 100$ | $n \leq 10^5$ | | 2 | $=0$ | 无 | | 3 | $=1$ | 无 | | 4 | $=2$ | 无 | | 5 | $\leq 100$ | $w = 1$，$ a_1 = 1$ | | 6 | $\leq 100$ | $w = 1$，$ a_1 = 1$ | | 7 | $\leq 100$ | $ \prod_{i = 1}^w (a_i + 1) \leq 10^5$ | | 8 | $\leq 100$ | $w \leq 16$ | | 9 | $\leq 100$ | 无 | | 10 | $\leq 100$ | 无 | 对于全部的测试点，保证 $1 \leq w \leq 10^3$，$2 \leq p_i \leq 10^9$，$1 \leq a_i \leq 10^9$。