A subarray is said to be balanced if the number of pairs \((i,\ i+1)\), such that \(A[i]\) is even and \(A[i+1]\) is odd, is equal to the number of pairs \((i,\ i+1)\) such that \(A[i]\) is odd and \(A[i+1]\) is even.

You are given an array \(A\) of \(N\) elements.

You are performing \(Q\) queries on it. In each query, you are given \(L\ R\ X\) in which you add \(X\) to all the elements in range \(L\) to \(R\) (inclusive). After each query, print the probability that if you randomly select a subarray in \(A\), then that subarray is balanced.

It can be proved that the probability is of the form \(\frac {P}{Q}\) where \(P\) and \(Q\) are both coprimes. Print \(PQ^{-1}\ modulo\ 1000000007\ (10^9+7)\) for each query.

Input format

• The first line contains an integer \(N\) denoting the number of elements in the array.
• The next line contains \(N\) space-separated integers.
• The next line contains an integer \(Q\) denoting the number of queries.
• The next Q lines contain three space-separated integers \(L\ R\ X\).

Output format

Print a single integer denoting the probability for each query.

Constraints
\(1 \le N,\ Q \le 1e5\\ 1 \le A[i],\ X \le 1e18\)