原本以为又是格路计数，结果是对每个长度都要计数，没法优化。
记 \(f_{i,j,k}\) 表示前 \(i\) 个数，当前前缀和为 \(j\)，最大前缀和为 \(k\)，则状态数为 \(O(n^3)\)，转移 \(O(1)\)。
这个状态不是很好优化，最大前缀和很烦。考虑能否钦定。
记 \(f_{i,j}\) 前 \(i\) 个前缀和距离钦定的 \(maxpre\) 还差为 \(j\) 的贡献和。发现还需要一维记录之前是否达到过 \(maxpre\)。
于是有思路 \(f_{i,j,0/1}\)。转移方程为:
\[f_{0,j,0}=h_i\\
f_{i,j,[j=0]|k}=p_if_{i-1,j+1,k}+(1-p_i)f_{i-1,j-1,k}
\]
\(ans_i=\sum_{j=0}^n f_{i,j,1}\)。
还有一种思路是，正难则反，\(f_{i,j}\) 表示 \([i,n]\) 的后缀中 \(maxpre\) 为 \(j\)，则每次的最大前缀和必定是从原本的拓展或是置为 0。
假设序列长度为 \(l\)。
\[f_{l+1,0}=1\\
f_{i,j}=p_if_{i+1,\max(j-1,0)}+(1-p_i)f_{i+1,j+1}
\]
则 \(ans=\sum_i h_if_{1,i}\)。
但这样固定长度需要 \(O(n)\)，总 \(O(n^3)\)。
考虑反推贡献，设 \(w_{i,j}\) 为 \(f_{i,j}\) 在 \(ans\) 中的系数。
\[w_{i,j}=p_iw_{i-1,\max(j-1,0)}+(1-p_i)w_{i-1,j_1}
\]
则长度为 \(ans_l=w_{l+1,0}\)，复杂度 \(O(n^2)\)。
Takanashi Rikka
// Problem: CF1810G The Maximum Prefix
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1810G
// Memory Limit: 250 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define fin(x) freopen(#x".in","r",stdin)
#define fout(x) freopen(#x".out","w",stdout)
#define fr(x) fin(x),fout(x);
#define Fr(x,y) fin(x),fout(y)
#define INPUT(_1,_2,FILE,...) FILE
#define IO(...) INPUT(__VA_ARGS__,Fr,fr)(__VA_ARGS__)
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define intz(x,z) memset((x),(z),sizeof((x)))
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
inline ll lowbit(ll x){return x&-x;}
#define fi first
#define se second
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
inline void cmx(auto &x,ll y){if(y>x)x=y;}
inline void cmn(auto &x,ll y){if(y<x)x=y;}
const int N=5005,mod=1e9+7;
#define int ll
int qp(int x,int y){int res=1;for(;y;y>>=1,x=x*x%mod)if(y&1)res=res*x%mod;return res;}
int f[N][N],x[N],y[N];
void UesugiErii(){int n;cin>>n;for(int i=1,X,Y,tmp;i<=n;i++)cin>>X>>Y,tmp=qp(Y,mod-2),x[i]=X*tmp%mod,y[i]=(Y-X)*tmp%mod;for(int i=0;i<=n;i++)cin>>f[1][i];for(int i=2;i<=n+1;i++)for(int j=0;j<=n;j++)f[i][j]=(f[i-1][max(j-1,0)]*y[i-1]%mod+f[i-1][j+1]*x[i-1]%mod)%mod;for(int i=2;i<=n+1;i++)cout<<f[i][0]<<' ';cout<<'\n';
}
signed main(){//cfast;int _=1;cin>>_;for(;_;_--)UesugiErii();return 0;
}