#include #include #include #include #include using namespace std; using mint=atcoder::modint; using dat=pair; dat op(dat a,dat b){return make_pair(a.first+b.first,a.second+b.second);} dat e(){return make_pair(mint::raw(0),0);} dat mp(mint f,dat x){x.first*=f.pow(x.second);return x;} mint cmp(mint f,mint g){return f*g;} mint id(){return mint::raw(1);} int N; int A[2<<17],B[2<<17]; mint f(int K) { atcoder::lazy_segtreeseg(N); vectorinitA(N),initAB(N); for(int i=0;isegA(initA),segAB(initAB); mint ans=0; for(int i=0;i+K<=N;i++) { mint cur=segAB.prod(0,i)-seg.prod(0,i).first; seg.set(i,make_pair(cur,1)); int l=max(0,i-K); seg.apply(0,l,A[i]+B[i]); seg.apply(l,i+1,A[i]); ans+=cur*segA.prod(i,i+K)*segAB.prod(i+K,N); } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int K; cin>>N>>K; for(int i=0;i>A[i]; for(int i=0;i>B[i]; cout<<(f(K)-f(K+1)).val()<