Problem source

104168D2 - Nested Sum (Hard Version)

Statement

Given an array of $$$n$$$ positive integers $$$a_{1}, a_{2},...,a_{n}$$$, find the value of $$$\sum_{i=1}^{n}\sum_{j=i+1}^{n}\sum_{k=j+1}^{n}a_{i}a_{j}a_{k}$$$ modulo $$$10^{9}+7$$$

Input

The first line of input contains an integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$).

The first line of each test case contains an integer $$$n$$$ ($$$1 \le t \le 10^{5}$$$), the size of the array.

The second line of each test case contains $$$n$$$ integers $$$a_{1}, a_{2},...,a_{n}$$$ ($$$1 \le t \le 10^{9}$$$), the elements of the array.

The sum of n over all test cases doesn't exceed $$$5\cdot 10^{5}$$$.

Output

For each test case output one line containing one integer, the sum described in the problem modulo $$$10^{9}+7$$$

Example

Input

3
3
1 1 1
4
1 2 3 4
5
5 4 3 1 2

Output

1
50
225

What I've done

I have tried to solve this problem for a hour but when I submit it, many testcase is WA:

Test 1: OK, 0 point(s)
Group G1: 0.0 point(s)
    Test 2: WRONG_ANSWER
    Test 3: WRONG_ANSWER
    Test 4: WRONG_ANSWER
    Test 5: WRONG_ANSWER
    Test 6: WRONG_ANSWER
    Test 7: WRONG_ANSWER
    Test 8: WRONG_ANSWER
    Test 9: WRONG_ANSWER
    Test 10: WRONG_ANSWER
    Test 11: WRONG_ANSWER
    Test 12: WRONG_ANSWER
    Test 13: WRONG_ANSWER
    Test 14: WRONG_ANSWER
    Test 15: WRONG_ANSWER
    Test 16: WRONG_ANSWER
    Test 17: WRONG_ANSWER
    Test 18: WRONG_ANSWER
    Test 19: WRONG_ANSWER
    Test 20: WRONG_ANSWER
    Test 21: WRONG_ANSWER
    Test 22: WRONG_ANSWER
    Test 23: WRONG_ANSWER
    Test 24: WRONG_ANSWER
    Test 25: WRONG_ANSWER
    Test 26: WRONG_ANSWER
    Test 27: WRONG_ANSWER
    Test 28: WRONG_ANSWER
    Test 29: WRONG_ANSWER
    Test 30: WRONG_ANSWER
    Test 31: WRONG_ANSWER
Group G2: 0.0 point(s)
    Test 32: WRONG_ANSWER
    Test 33: WRONG_ANSWER
    Test 34: WRONG_ANSWER
    Test 35: WRONG_ANSWER
    Test 36: WRONG_ANSWER
    Test 37: WRONG_ANSWER
    Test 38: WRONG_ANSWER
    Test 39: WRONG_ANSWER
    Test 40: WRONG_ANSWER
    Test 41: WRONG_ANSWER
    Test 42: WRONG_ANSWER
    Test 43: WRONG_ANSWER
    Test 44: WRONG_ANSWER
    Test 45: WRONG_ANSWER
    Test 46: WRONG_ANSWER
    Test 47: WRONG_ANSWER
    Test 48: WRONG_ANSWER
    Test 49: WRONG_ANSWER
    Test 50: WRONG_ANSWER
    Test 51: WRONG_ANSWER
    Test 52: WRONG_ANSWER
    Test 53: WRONG_ANSWER
    Test 54: WRONG_ANSWER
    Test 55: WRONG_ANSWER
    Test 56: WRONG_ANSWER
    Test 57: WRONG_ANSWER
    Test 58: WRONG_ANSWER
    Test 59: WRONG_ANSWER
    Test 60: WRONG_ANSWER
    Test 61: WRONG_ANSWER
    Test 62: WRONG_ANSWER
    Test 63: WRONG_ANSWER
    Test 64: WRONG_ANSWER
    Test 65: WRONG_ANSWER
    Test 66: WRONG_ANSWER
    Test 67: WRONG_ANSWER
    Test 68: WRONG_ANSWER
    Test 69: WRONG_ANSWER
    Test 70: WRONG_ANSWER
    Test 71: WRONG_ANSWER
    Test 72: WRONG_ANSWER
    Test 73: WRONG_ANSWER
    Test 74: WRONG_ANSWER
    Test 75: WRONG_ANSWER
    Test 76: WRONG_ANSWER
    Test 77: WRONG_ANSWER
    Test 78: WRONG_ANSWER
    Test 79: WRONG_ANSWER
    Test 80: WRONG_ANSWER
    Test 81: WRONG_ANSWER
    Test 82: OK
    Test 83: OK
    Test 84: OK
    Test 85: OK
    Test 86: OK
    Test 87: OK
    Test 88: OK
    Test 89: OK
    Test 90: OK
    Test 91: OK
    Test 92: OK
    Test 93: OK
    Test 94: OK
    Test 95: OK
    Test 96: OK
    Test 97: OK
    Test 98: OK
    Test 99: OK
    Test 100: OK
    Test 101: OK

=
Points: 0.0

I don't know why my code failed, can you find out my mistake? This is my code.

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define multitest int _T; cin >> _T; while (_T--)

const int MOD = 1000000007;

int add(int x, int y)
{
    return (x + y) % MOD;
}

int mul(int x, int y)
{
    return (x * y) % MOD;
}

void solve()
{
    int n;
    cin >> n;

    int a[n];
    int pre1[n+1];
    pre1[0] = 0;

    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        pre1[i+1] = add(a[i], pre1[i]);
    }

    int pre2[n-1];
    pre2[0] = 0;
    for (int i = 1; i < n-1; ++i)
        pre2[i] = add(pre2[i-1], mul(a[i], pre1[n] - pre1[i+1]));

    int ans = 0;
    for (int i = 0; i < n-2; ++i)
        ans += mul(a[i], pre2[n-2] - pre2[i]);

    cout << ans << endl;
}

signed main()
{
    fastio;
    multitest
        solve();
}

Thank you in advance ❤️