P17819 二维积性函数求和（many queries）

板子。

定义二维数论函数 $f(x,y)$ 是积性函数，当且仅当对于所有 $\gcd(ab,cd)=1$，都有 $f(ac,bd)=f(a,b)f(c,d)$。 给你一个二维积性函数 $f$，满足 $f(x,y)=f(y,x)$。 $q$ 次询问，每次给定 $n,m$，求 $\sum_{i=1}^n\sum_{j=1}^mf(i,j)$。答案对 $10^9+7$ 取模。

记 $\pi(n)$ 为 $1\sim n$ 的质数个数，$p_i$ 为第 $i$ 个质数。 第一行两个整数 $N,q$。 之后 $\pi(N)$ 行，对于第 $i$ 行，记 $l=\lfloor\log_{p_i}N\rfloor+1$，一行读入 $l^2-1$ 个整数，第 $j$ 个整数为 $f(p_i^{\lfloor\frac{j}{l}\rfloor},p_i^{j\bmod l})$。保证 $f(x,y)=f(y,x)$。 接下来 $q$ 行，每行两个整数 $n,m$。

$q$ 行，每行一个整数表示答案对 $10^9+7$ 取模后的结果。

### 样例解释 | $f(x,y)$ | $y=1$ | $y=2$ | $y=3$ | $y=4$ | $y=5$ | $y=6$ | |:-:|:-:|:-:|:-:|:-:|:-:|:-:| | $x=1$ | $1$ | $2$ | $7$ | $3$ | $9$ | $14$ | | $x=2$ | $2$ | $4$ | $14$ | $5$ | $18$ | $28$ | | $x=3$ | $7$ | $14$ | $8$ | $21$ | $63$ | $16$ | | $x=4$ | $3$ | $5$ | $21$ | $6$ | $27$ | $35$ | | $x=5$ | $9$ | $18$ | $63$ | $27$ | $10$ | $126$ | | $x=6$ | $14$ | $28$ | $16$ | $35$ | $126$ | $32$ | ### 数据范围 $1\le N,q\le 1.5\times10^5$，$1\le n,m\le N$，$0\le f(p_i^a,p_i^b)\le 10^9$。 | 子任务编号 | $N=$ | $q=$ | 分值 | |:-:|:-:|:-:|:-:| | $1$ | $5000$ | $5000$ | $10$ | | $2$ | $30000$ | $30000$ | $20$ | | $3$ | $60000$ | $60000$ | $20$ | | $4$ | $100000$ | $100000$ | $25$ | | $5$ | $150000$ | $150000$ | $25$ |