【集训队作业2018】石像
复活节岛上有 $n$ 个石像，每个石像的高度是一个 $[1,m]$ 之间的整数。设第 $i$ 个石像的高度为 $a_i$。
实际上，还有很多个像复活节岛一样的岛屿，一共有 $m^n$ 个（包括复活节岛），每个岛上都有 $n$ 个石像。由于某些原因，每个岛屿（包括复活节岛）都是独一无二的，即没有两个岛屿上的石像的高度是完全相同的。
每个岛上都聚集着很多能量，准确来说，有 $(\sigma_0(\gcd(a_1,a_2,\ldots,a_n)^3))^3$ 点能量。其中 $\sigma_0(n)$ 表示 $n$ 的因子个数。
几百年前，黑恶势力登陆地球，诅咒了所有岛屿：一共有 $k$ 个诅咒。第 $i$ 个诅咒可以用两个整数 $x_i,y_i$ 来表示，表示第 $x_i$ 个石像的高度不能超过第 $y_i$ 个石像的高度，即 $a_{x_i}\leq a_{y_i}$。如果一个岛上的石像的高度满足所有诅咒的要求，那么就不会发生任何事，否则整个岛屿就会被毁灭。所有岛上的诅咒都是相同的。
有些岛屿因此消失了，剩下的岛屿上的人把能量汇集在一起，击败了黑恶势力。
作为一名考古学家，你想知道剩下的岛屿的能量值的和是多少。
答案可能会很大，所以你只需要求出答案模 $2^{32}$ 的值。
一句话题意：求 $$ \left(\sum_{a_1=1}^m\sum_{a_2=1}^m\cdots\sum_{a_n=1}^m{\left(\sigma_0\left(\gcd\left(a_1,a_2,\ldots,a_n\right)^3\right)\right)}^3\prod_{i=1}^k\left[a_{x_i}\leq a_{y_i}\right]\right)\bmod 2^{32} $$
输入格式
第一行有三个整数 $n,m,k$。
接下来 $k$ 行每行有两个整数：第 $i$ 行的两个整数为 $x_i,y_i$。
输出格式
一个整数：答案。
2 2 1
1 2
66
总共有三种不同的情况：
- $a_1=1,a_2=1,s=1,\sigma_0(s^3)^3=1$。
- $a_1=1,a_2=2,s=1,\sigma_0(s^3)^3=1$。
- $a_1=2,a_2=2,s=2,\sigma_0(s^3)^3=64$。
5 10 4
1 2
1 3
2 4
2 5
54283
限制与约定
| 子任务 | 分值 | $n$ | $m$ | $k$ |
|---|---|---|---|---|
| $1$ | $5$ | $\leq 5$ | $\leq 10$ | $\leq n(n-1)$ |
| $2$ | $15$ | $\leq 13$ | $\leq 13$ | |
| $3$ | $30$ | $\leq 20$ | $\leq {10}^7$ | |
| $4$ | $30$ | $\leq {10}^{10}$ | $=0$ | |
| $5$ | $20$ | $\leq n(n-1)$ |
对于所有数据：$1\leq n\leq 20,1\leq m\leq {10}^{10},0\leq k\leq n(n-1)$，不存在两个相同的诅咒。
时间限制：$\texttt{4s}$
空间限制：$\texttt{512MB}$