There are $n$ statues on Easter Island, and the height of each statue is an integer in the range $[1, m]$. Let the height of the $i$-th statue be $a_i$.

In fact, there are many islands like Easter Island, totaling $m^n$ islands (including Easter Island itself), each with $n$ statues. For various reasons, every island (including Easter Island) is unique, meaning no two islands have the exact same set of statue heights.

Each island possesses a certain amount of energy, specifically $(\sigma_0(\gcd(a_1, a_2, \ldots, a_n)^3))^3$ units of energy, where $\sigma_0(n)$ denotes the number of divisors of $n$.

Centuries ago, dark forces landed on Earth and cursed all the islands. There are $k$ curses in total. The $i$-th curse is represented by two integers $x_i, y_i$, meaning the height of the $x_i$-th statue cannot exceed the height of the $y_i$-th statue, i.e., $a_{x_i} \leq a_{y_i}$. If the statue heights on an island satisfy all the curses, nothing happens; otherwise, the entire island is destroyed. The curses are the same for all islands.

Some islands disappeared as a result, and the people on the remaining islands pooled their energy together to defeat the dark forces.

As an archaeologist, you want to know the sum of the energy values of the remaining islands.

The answer may be very large, so you only need to output the answer modulo $2^{32}$.

In short: calculate $$ \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} $$

Input

The first line contains three integers $n, m, k$.

The next $k$ lines each contain two integers: the $i$-th line contains $x_i, y_i$.

Output

A single integer: the answer.

Examples

Input 1

2 2 1
1 2

Output 1

66

Note 1

There are three valid cases:

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

5 10 4
1 2
1 3
2 4
2 5

Output 2

54283

Constraints

For all data: $1 \leq n \leq 20, 1 \leq m \leq {10}^{10}, 0 \leq k \leq n(n-1)$, and no two curses are identical.