The score of an Array \(S\) of length \(N \) is defined as \(\sum_{i=0}^{N-2} S_i \cdot S_{i+1}\), i.e. sum of product of every consecutive pair of elements.
Given an Array \(arr\) of length \(N\) find the sum of scores of every subsequence of \(arr\) of length atleast \(2\), return the sum modulo \(10^9 + 7\).
A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.
Input Format:
- First line contains an integer \(T\) denoting the number of test cases.
- First line of each testcase contains an integer \(N\) denoting length of \(arr\).
- Next line contains \(N \) space-seperated integer, denoting the elements of \(arr\).
Output Format:
- For each testcase, print the sum of scores of every subsequence of \(arr\) having length atleast \(2\), modulo \(10^9 + 7\).
Constraints:
- \(1 \le T \le 10\)
- \(2 \le N \le 5 \times 10^5\)
- \(0 \le arr[i] \le 10^4\)
5 4 1 1 2 3 7 1 1 1 1 1 1 1 4 1 0 1 0 10 1 2 3 4 5 6 7 8 9 10 10 9990 9991 9992 9993 9994 9995 9996 9997 9998 9999
49 321 2 142836 249469973
First Sample Case
First Subsequence is \([1, 1]\)
Score is \(1 \times 1\) = \(1\)
Second Subsequence is \([1, 2]\) and appears \(2\) times
Score is \(1 \times 2\) = \(2\) added \(2\) times
Third Subsequence is \([1, 3]\) and appears \(2\) times
Score is \(1 \times 3\) = \(3\) added \(2\) times
Fourth Subsequence is \([2, 3]\)
Score is \(2 \times 3\) = \(6\)
Fifth Subsequence is \([1, 1, 2]\)
Score is \(1 \times 1 + 1 \times 2\) = \(3\)
Sixth Subsequence is \([1, 1, 3]\)
Score is \(1 \times 1 + 1 \times 3\) = \(4\)
Seventh Subsequence is \([1, 2, 3]\) and appears \(2\) times
Score is \(1 \times 2 + 2 \times 3\) = \(8\) added \(2\) times
Eighth Subsequence is \([1, 1, 2, 3]\)
Score is \(1 \times 1 + 1 \times 2 + 2 \times 3\) = \(9\)
Sum of score for every subsequence = \(49\)
Second Sample Case
First Subsequence is \([1, 1]\) and appears \(21\) times
Score is \(1 \times 1\) = \(1\) added \(21\) times
Second Subsequence is \([1, 1, 1]\) and appears \(35\) times
Score is \(1 \times 1 + 1 \times 1\) = \(2\) added \(35\) times
Third Subsequence is \([1, 1, 1, 1]\) and appears \(35\) times
Score is \(1 \times 1 + 1 \times 1 + 1 \times 1\) = \(3\) added \(35\) times
Fourth Subsequence is \([1, 1, 1, 1, 1]\) and appears \(21\) times
Score is \(1 \times 1 + 1 \times 1 + 1 \times 1 + 1 \times 1\) = \(4\) added \(21\) times
Fifth Subsequence is \([1, 1, 1, 1, 1, 1]\) and appears \(7\) times
Score is \(1 \times 1 + 1 \times 1 + 1 \times 1 + 1 \times 1 + 1 \times 1\) = \(5\) added \(7\) times
Sixth Subsequence is \([1, 1, 1, 1, 1, 1, 1]\)
Score is \(1 \times 1 + 1 \times 1 + 1 \times 1 + 1 \times 1 + 1 \times 1 + 1 \times 1\) = \(6\)
Sum of score for every subsequence = \(321\)
Third Sample Case
First Subsequence is \([1, 1]\)
Score is \(1 \times 1\) = \(1\)
Second Subsequence is \([1, 1, 0]\)
Score is \(1 \times 1 + 1 \times 0\) = \(1\)
Every other subsequence has score \(0 \)
Sum of score for every subsequence = \(2\)
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
Login to unlock the editorial
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