复活节岛上有 $n$ 个石像，每个石像的高度是一个 $[1,m]$ 之间的整数。设第 $i$ 个石像的高度为 $a_i$。

实际上，还有很多个像复活节岛一样的岛屿，一共有 $m^n$ 个（包括复活节岛），每个岛上都有 $n$ 个石像。由于某些原因，每个岛屿（包括复活节岛）都是独一无二的，即没有两个岛屿上的石像的高度是完全相同的。

每个岛上都聚集着很多能量，准确来说，有 $({\sigma }_0(gcd(a_1,a_2,\dots ,a_n{)}^3){)}^3$ 点能量。其中 ${\sigma }_0(n)$ 表示 $n$ 的因子个数。

几百年前，黑恶势力登陆地球，诅咒了所有岛屿：一共有 $k$ 个诅咒。第 $i$ 个诅咒可以用两个整数 $x_i,y_i$ 来表示，表示第 $x_i$ 个石像的高度不能超过第 $y_i$ 个石像的高度，即 $a_{x_i}\le a_{y_i}$。如果一个岛上的石像的高度满足所有诅咒的要求，那么就不会发生任何事，否则整个岛屿就会被毁灭。所有岛上的诅咒都是相同的。

有些岛屿因此消失了，剩下的岛屿上的人把能量汇集在一起，击败了黑恶势力。

作为一名考古学家，你想知道剩下的岛屿的能量值的和是多少。

答案可能会很大，所以你只需要求出答案模 $2^{32}$ 的值。

一句话题意：求 $$(\sum _{a_1=1}^m\sum _{a_2=1}^m\cdots \sum _{a_n=1}^m{\left({\sigma }_0(gcd{(a_1,a_2,\dots ,a_n)}^3)\right)}^3\prod _{i=1}^k[a_{x_i}\le a_{y_i}])mod{2}^{32}$$

输入格式

第一行有三个整数 $n,m,k$。

接下来 $k$ 行每行有两个整数：第 $i$ 行的两个整数为 $x_i,y_i$。

输出格式

一个整数：答案。

样例一

input

2 2 1
1 2

output

66

explanation

总共有三种不同的情况：

• $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$。

样例二

input

5 10 4
1 2
1 3
2 4
2 5

output

54283

限制与约定

对于所有数据：$1\le n\le 20,1\le m\le {10}^{10},0\le k\le n(n-1)$，不存在两个相同的诅咒。

时间限制：$\mathtt{\text{4s}}$

空间限制：$\mathtt{\text{512MB}}$

下载

样例数据下载