复活节岛上有 $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$。

输出格式

一个整数：答案。

样例一

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\leq n\leq 20,1\leq m\leq {10}^{10},0\leq k\leq n(n-1)$，不存在两个相同的诅咒。