An array is said to be special, if we can break it down into subarrays where every subarray (length > 1) starts and ends with 0 and rest all other numbers are 1.
Given N binary arrays.
Sam decided to write down all the distinct prefix subarrays of the given N binary arrays on a paper (he'll write distinct prefix only). After that he counts the number of special subarrays in every prefix and sum that up (a special subarray will be counted as many times as it is contained in each prefix).
Find the sum found by Sam modulo 109+7.
Input Format:
Output Format:
Sum found by Sam modulo 109+7
Constraints:
1≤N≤1031≤S[i]≤1051≤∑Ni=1S[i]≤2×106
There are 8 different unqiue prefixes, count of special subarray in each prefix is listed below