#include using namespace std; #include using namespace atcoder; using mint = modint998244353; using fps = vector; pair SumfpsFraction(vector A,vector B){ //次数の和=n O(nlog^2n). //ΣAi/Biを求める 分割統治でO(nlog^2n). //a/b+c/d = (ad+bc)/bd 面倒なのでvectorは用意せずfpsだけ; assert(A.size() == B.size() && A.size()); int n = A.size(); auto comp = [&](int a,int b) -> bool {return A[a].size()+B[a].size()>A[b].size()+B[b].size();}; priority_queue,decltype(comp)> Q(comp); for(int i=0; i 1){ int p = Q.top(); Q.pop(); int q = Q.top(); Q.pop(); fps num = convolution(A.at(p),B.at(q)); fps num2 = convolution(B.at(p),A.at(q)); if(num.size() < num2.size()) num.resize(num2.size()); for(int i=0; i> N >> S; vector A(N),B(N); mint divS = mint(1)/S; for(int i=0; i> p; mint one = divS*p,two = one*one; A.at(i) = {two}; B.at(i) = {1,one}; } auto [n,d] = SumfpsFraction(A,B); mint answer = 0,fac = 1; for(int i=0; i