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\)
6 7 111 2 13110 345 17017 851 1 2 2 3 3 1 3 4 4 5 3 5 5 6
1
Node numbers $$3$$ and $$5$$ are weak nodes. If we consider all of their subsets product then only one subset {3 , 5} which has the product $$13110 \times 17017 = 223092870$$ is divisible by all the prime numbers less than $$25$$. Hence $$1$$ is the answer.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor