[Nested Sum] Can you help me with this problem?

[Nested Sum] Can you help me with this problem?

Problem source

104168D2 - Nested Sum (Hard Version)

Statement

Given an array of positive integers , find the value of modulo

Input

The first line of input contains an integer ().

The first line of each test case contains an integer (), the size of the array.

The second line of each test case contains integers (), the elements of the array.

The sum of n over all test cases doesn't exceed .

Output

For each test case output one line containing one integer, the sum described in the problem modulo

Example

Input

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

Output

What I've done

I have tried to solve this problem for an 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 ❤️