You are given $N$ nodes with the following information:

• The nodes are connected by $M$ bidirectional edges.
• Each node has a value $V_i$ associated with it.
• A node is called a weak node if the connections between some other nodes are broken when that node is deleted and any alternate connections are not present.

Write a program to tell the number of subsets from all the possible subsets of weak nodes, which on getting their values multiplied gives a number which is divisible by all primes less than $25$.

Since the answer can be large, print the answer Modulo $10^9+7$.

Input format

• First line: Two space-separated integers $N$ and $M$
• Second line: $N$ space-separated integers denoting the values of the nodes
• Next $M$ lines: Two space-separated integers $U$ and $V$ denoting an edge between $U$ and $V$

Output format

Print the required answer Modulo $10^9+7$.

Constraints

$1 \le N, M \le 5 \times 10^4$
$1 \le U, V \le N$
$1 \le V \le 10^9$