Product of Supercomputer Table

Doris generated an \(n \times m\) table using her teacher's supercomputer. The element in the \(i\)-th row and \(j\)-th column is \(f_{\gcd(i,j)}\), where \(\gcd(i,j)\) denotes the greatest common divisor of \(i\) and \(j\). There are \(n \times m\) numbers in the table and Doris wants to know the product of all these numbers. Since the answer might be very large, output the result modulo \(10^9+7\).

inputFormat

The input consists of two parts:

• The first line contains two integers \(n\) and \(m\).
• The second line contains \(\min(n, m)\) integers: \(f_1, f_2, \dots, f_{\min(n, m)}\). These values define the table cell values in the following way: the element at cell \((i,j)\) is \(f_{\gcd(i,j)}\).

outputFormat

Output a single integer, the product of all \(n \times m\) numbers in the table modulo \(10^9+7\).

sample

3 3
1 2 3

6