A tree is given having N nodes numbered from 1 to N, rooted at 1. We are also given a positive integer M, the value of each node can be anything from 1 to M.

Let's say a tree is beautiful if there is at least one leaf node such that gcd of values of each node on the path from that leaf node to the root node is greater than 1.

Now, we need to calculate the number of ways in which we can assign values to all the nodes such that we get a beautiful tree. Two ways are different if there is at least one node having different values. We are supposed to return the answer modulo 1e9 + 7.

Constraints:

• 1 ≤ N ≤ 1e5
• 1 ≤ M ≤ 20

Note: This problem is not from any running contest, it was asked in the campus placement test.

Initially, we are given an Array of N non-negative integers. After that, we have to perform Q queries on it and finally print the modified Array. Each query looks like this: L R X, here we have to change the array elements from L to R (Both inclusive) to AND of X and previous element. That means Ai changes to (X & Ai).

Constraints:

• 1 ≤ N ≤ 2*10^5

• 0 ≤ Ai ≤ 10^9

• 1 ≤ Q ≤ 2*10^5

• 1 ≤ L, R ≤ N

• 0 ≤ X ≤ 10^9

Note: If the operation were SUM instead of AND, then it can be easily solved by using the Difference array, but I am unable to think something similar for AND operation. Help will be really appreciated. :) Thanks in advance.