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 PQ where P and Q are both coprimes. Print PQ−1 modulo 1000000007 (109+7) for each query.
Input format
Output format
Print a single integer denoting the probability for each query.
Constraints
1≤N, Q≤1e51≤A[i], X≤1e18
After Query 1 , array is 14 3 58 252 63.
Balanced Subarrays are : [1], [2], [3], [4], [5] , [1,3], [1,4], [3,4] , [2,5] .
Probability = 9 / 15
Output is modulo 10^9 + 7.