传送门。
神仙题，做了半年。
整体是不好做的，考虑每个\(w_i\)对整体的贡献。记\(s_i=\sum_{i=1}^{i}a_i\)，\(d_i=\sum_{i=1}^{i}b_i\)，当且仅当\(s_i\neq d_i\)时，才会有货物流通\(i\)号点。所以总体的答案为：
最直接的想法是枚举\(d_i\)。那么一个\(|d_i-c_i|\)会被计算多少次？ 相当于给前\(i\)个点分配\(b_i\)，问题可以看成，一共\(d_i\)个相同小球，放进\(i\)个不同盒子，可以为空，后面\(n-i\)个点类似，运用插板法可以得到：
遇到绝对值先拆掉。到这里成功拆掉绝对值，观察最外层括号里面，那个加号两边式子的形式是相同的。于是接下来只讨论加号前面的式子。系数先扔了。
这个减号两边是两个完全不同的式子。左边那个不带枚举的系数，应该是更好处理，所以要是能把减号右边化成左边的样子就好了。 那么我们不妨设\(f(n,S,i,k)=\sum_{j=1}^{k}C_{i+j-1}^{i-1}C_{n-i+S-j-1}^{n-i-1}\)，注意这里\(i\)已经是一个常数了。现在来看减号右边。这个\(j\)在这里是非常不好的，尝试把它变成\(i\)。来看下面的推导：
神奇的事情发生了，减号右边竟然变成了
注意，下面那个式子\(j\)从\(1\)开始枚举，因为可以发现\(j=0\)时\(\sum\)右边结果为\(0\)，所以给他踢了。为什么要有这一步，来看下面：
这样问题就得到了解决。最初的式子中，加号左边被我们化成了\(2s_if(n,S,i,s_i)-2if(n+1,S-1,i+1,s_i-1)\)。减号右边采取类似的做法，整个括号内部就变成了：
整个过程\(i\)递增，\(s_i\)递增，我们可以用类似指针移动的方法，每当\(s_i\)增大时，按照\(f\)的定义累加过来就可以了。可是当\(i\)增大时要怎么办呢？
于是本题最神仙的一步来了。再推下去难以有新的头绪，于是我们重新回到组合意义上来。根据前文，\(f(n,S,i,k)\)表示的意义可以抽象为给\(n\)个盒子分配\(S\)个小球，且前\(i\)个盒子分配最多\(k\)个小球的方案数。这个等价于从前往后数第\(k+1\)个小球放在了从第\(i+1\)个盒子开始往后的盒子中。枚举它放在了第\(j\)个盒子里，那么除这个球外前\(j\)个盒子里放了\(k\)个球（注意这个球是不能考虑进去的，因为我们枚举固定了这个球的位置），同样运用插板法，可以得到：
这个式子要小心别推错了，第\(j\)个盒子也是可以放前后别的球的。这一步启示我们，思路卡住的时候不妨换个角度，要明白我们想要干的是什么事儿。上面两种\(f\)的表示方法只是计算方式不同，对应结果是一样的，可以同时来做。于是\(i\)增加的时候把前面不必要的减去，也是同样的维护方法。对于上面括号内部\(f\)的四种形式分别维护一下就可以了。
演草纸是很有必要的。推的时候不能急，各种情况都要考虑清楚。
int T;
int n, a[N];
ll s[N], jc[N], inv[N], w[N];ll quick(ll x, ll y){ll rs = 1ll;while(y){if(y & 1) (rs *= x) %= mod;(x *= x) %= mod;y >>= 1;}return rs;
}ll C(ll x, ll y){if(x < y || x < 0 || y < 0) return 0;return jc[x] * inv[y] % mod * inv[x - y] % mod;
}struct F{ll val = 0ll;ll nowi, nowk, nn, ss;void giv(ll Nn, ll Ss, ll ii, ll kk){nowi = ii, nowk = kk;nn = Nn, ss = Ss;val = 0ll;for(int j = 0; j <= kk; j++){val += C(ii + j - 1, ii - 1) * C(nn - ii + ss - j - 1, nn - ii - 1) % mod;val %= mod;}return;}void chg_k(ll k){if(k <= nowk) return;ll i = nowi;for(ll j = nowk + 1; j <= k; j++){val += C(i + j - 1, i - 1) * C(nn - i + ss - j - 1, nn - i - 1) % mod;val %= mod;nowk = j;}return;}void chg_i(ll i){if(i <= nowi) return;ll k = nowk;for(ll j = nowi + 1; j <= i; j++){val -= C(j + k - 1, j - 1) * C(nn - j + ss - k - 1, nn - j) % mod;(val += mod) %= mod;nowi = j;}return;}
}f1, f2, f3, f4;void pre(){jc[0] = inv[0] = 1ll;for(int i = 1; i <= N - 5; i++) jc[i] = jc[i - 1] * i % mod;inv[N - 5] = quick(jc[N - 5], mod - 2);for(int i = N - 6; i; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
}void work(){n = read();for(int i = 1; i <= n; i++) a[i] = read();for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];for(int i = 1; i < n; i++) w[i] = readll();ll S = s[n];f1.giv(n + 1, S - 1, 1, S - 1);f2.giv(n, S, 1, S);f3.giv(n, S, 1, 0);f4.giv(n + 1, S - 1, 1, -1);ll res = 0ll;for(int i = 1; i < n; i++){f3.chg_k(s[i]);f4.chg_k(s[i] - 1);f1.chg_i(i + 1);f2.chg_i(i);f3.chg_i(i);f4.chg_i(i + 1);ll Val = 0ll;Val += i * f1.val % mod;Val %= mod;Val -= s[i] * f2.val % mod;(Val += mod) %= mod;Val += 2ll * s[i] % mod * f3.val % mod;Val %= mod;Val -= 2ll * i % mod * f4.val % mod;(Val += mod) %= mod;res += Val * w[i] % mod;(res += mod) %= mod;}printf("%lld\n", (res + mod) % mod);
}signed main(){pre();T = read();while(T--) work();return 0;
}
累死了。