E.羊工八刀（预处理+前缀和优化）

思路：暴力枚举O(n^2)的复杂度显然会TLE。 我们可以将每个人位置预处理出来,再去计算每个位置能提供的贡献。 显然对于$po{s}_{i}pos\_i$,其贡献为： $(po{s}_i-po{s}_1{)}^2+(po{s}_i-po{s}_2{)}^2+(po{s}_i-po{s}_3{)}^2+\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}+(po{s}_i-po{s}_{i-1}{)}^2(pos\_i-pos\_1)^\{2\}+(pos\_i-pos\_2)^\{2\}+(pos\_i-pos\_3)^\{2\}+....+(pos\_i-pos\_\{i-1\})^\{2\}$

可以将其变形为：$(po{s}_i{)}^2\ast (i-1)+[(po{s}_1{)}^2+(po{s}_2{)}^2+\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}+(po{s}_{i-1}{)}^2]-2\ast po{s}_i\ast (po{s}_1+po{s}_2+\mathrm{.}\mathrm{.}\mathrm{.}+po{s}_{i-1})(pos\_i)^\{2\}*(i-1)+[(pos\_1)^\{2\}+(pos\_2)^\{2\}+....+(pos\_\{i-1\})^\{2\}]-2*pos\_i*(pos\_1+pos\_2+...+pos\_\{i-1\})$ 显然前缀和预处理可以O（n）实现总贡献的计算。

code：

typedef long long ll;
using namespace std;
const int mod = 1e9 + 7, N = 1e6 + 10;
ll a[N], sum[N], sum2[N];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef ak
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int t;
    cin >> t;
    while (t--)
    {
        memset(sum, 0, sizeof sum);
        memset(sum2, 0, sizeof sum2);
        memset(a, 0, sizeof a);
        int n;
        cin >> n;
        string s;
        cin >> s;
        int idx = 1;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == '1')
            {
                a[idx++] = i + 1;
            }
        }
        for (int i = 1; i < idx; i++)
        {
            sum[i] = sum[i - 1] + a[i] * a[i];
            sum[i] %= mod;
            sum2[i] += a[i] + sum2[i - 1];
            sum2[i] %= mod;
        }
        ll ans = 0;
        for (int i = 1; i < idx; i++)
        {
            ll x = a[i] * a[i] * (i - 1) + sum[i - 1] - 2 * sum2[i - 1] * a[i];
            ans += x;
            ans %= mod;
        }

        cout << ans << endl;
    }
    return 0;
}