题目背景

题目来源：$2014$ 年湖北省队互测Week1

资源来源：链接

题目描述

有一天 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$ 的质因数分解式。

第一行有用空格隔开的一个非负整数 $d$, 一个正整数 $w$。 接下来 $w$ 行，每行有两个用空格隔开的正整数 $p_i$, $α_i$。(保证 $p_i$ 为素数且互不相同)

输出格式

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

3 2 
2 1 
5 1

1100

提示

数据规模与约定

各测试点信息如下表

对于全部的测试点，保证 $1 \leq w \leq 10^3$，$2 \leq p_i \leq 10^9$，$1 \leq a_i \leq 10^9$。