P17818 gcd sum?

$q$ 次询问，每次给定 $l_1,r_1,l_2,r_2$，求 $\sum_{i=l_1}^{r_1}\sum_{j=l_2}^{r_2}\gcd(i,j)$，答案对 $10^9+7$ 取模。

第一行两个整数 $N,q$。 接下来 $q$ 行，每行四个整数 $l_1,r_1,l_2,r_2$。

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

### 数据范围 $1\le N,q\le 3\times10^5$，$1\le l_1\le r_1\le N$，$1\le l_2\le r_2\le N$。 | 子任务编号 | $N=$ | $q=$ | 分值 | |:-:|:-:|:-:|:-:| | $1$ | $50000$ | $50000$ | $10$ | | $2$ | $150000$ | $150000$ | $40$ | | $3$ | $300000$ | $300000$ | $50$ |