#include using namespace std; using int64 = long long; constexpr int64 MOD = 998244353; /* * @title ModInt * @docs md/util/ModInt.md */ template class ModInt { public: long long x; constexpr ModInt():x(0) {} constexpr ModInt(long long y) : x(y>=0?(y%mod): (mod - (-y)%mod)%mod) {} ModInt &operator+=(const ModInt &p) {if((x += p.x) >= mod) x -= mod;return *this;} ModInt &operator+=(const long long y) {ModInt p(y);if((x += p.x) >= mod) x -= mod;return *this;} ModInt &operator+=(const int y) {ModInt p(y);if((x += p.x) >= mod) x -= mod;return *this;} ModInt &operator-=(const ModInt &p) {if((x += mod - p.x) >= mod) x -= mod;return *this;} ModInt &operator-=(const long long y) {ModInt p(y);if((x += mod - p.x) >= mod) x -= mod;return *this;} ModInt &operator-=(const int y) {ModInt p(y);if((x += mod - p.x) >= mod) x -= mod;return *this;} ModInt &operator*=(const ModInt &p) {x = (x * p.x % mod);return *this;} ModInt &operator*=(const long long y) {ModInt p(y);x = (x * p.x % mod);return *this;} ModInt &operator*=(const int y) {ModInt p(y);x = (x * p.x % mod);return *this;} ModInt &operator^=(const ModInt &p) {x = (x ^ p.x) % mod;return *this;} ModInt &operator^=(const long long y) {ModInt p(y);x = (x ^ p.x) % mod;return *this;} ModInt &operator^=(const int y) {ModInt p(y);x = (x ^ p.x) % mod;return *this;} ModInt &operator/=(const ModInt &p) {*this *= p.inv();return *this;} ModInt &operator/=(const long long y) {ModInt p(y);*this *= p.inv();return *this;} ModInt &operator/=(const int y) {ModInt p(y);*this *= p.inv();return *this;} ModInt operator=(const int y) {ModInt p(y);*this = p;return *this;} ModInt operator=(const long long y) {ModInt p(y);*this = p;return *this;} ModInt operator-() const {return ModInt(-x); } ModInt operator++() {x++;if(x>=mod) x-=mod;return *this;} ModInt operator--() {x--;if(x<0) x+=mod;return *this;} ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } ModInt operator^(const ModInt &p) const { return ModInt(*this) ^= p; } bool operator==(const ModInt &p) const { return x == p.x; } bool operator!=(const ModInt &p) const { return x != p.x; } ModInt inv() const {int a=x,b=mod,u=1,v=0,t;while(b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);} return ModInt(u);} ModInt pow(long long n) const {ModInt ret(1), mul(x);for(;n > 0;mul *= mul,n >>= 1) if(n & 1) ret *= mul;return ret;} friend ostream &operator<<(ostream &os, const ModInt &p) {return os << p.x;} friend istream &operator>>(istream &is, ModInt &a) {long long t;is >> t;a = ModInt(t);return (is);} }; using modint = ModInt; /* * @title DisjointSparseTable * @docs md/segment/DisjointSparseTable.md */ template class DisjointSparseTable{ public: using TypeNode = typename Operator::TypeNode; size_t depth; size_t length; vector node; vector msb; DisjointSparseTable(const vector& vec) { for(depth = 0;(1<>j) msb[i] = j; //init value node.resize(depth*length,Operator::unit_node); for(int i = 0; i < vec.size(); ++i) node[i] = vec[i]; for(int i = 1; i < depth; ++i) { for(int r = (1<r||l<0||length<=r) ? Operator::unit_node: (l==r ? node[l] : Operator::func_node(node[msb[l^r]*length+l],node[msb[l^r]*length+r])); } }; //sum template struct NodeSum { using TypeNode = T; inline static constexpr TypeNode unit_node = 0; inline static constexpr TypeNode func_node(TypeNode l,TypeNode r){return l+r;} }; modint inv2 = modint(2).inv(); modint inv4 = modint(4).inv(); modint inv6 = modint(6).inv(); modint sigma_k1(modint n) { return n*(n+1)*inv2; } modint sigma_k2(modint n) { return n*(n+1)*(n*2+1)*inv6; } modint sigma_k3(modint n) { return n*n*(n+1)*(n+1)*inv4; } /** * @url * @est */ int main() { cin.tie(0);ios::sync_with_stdio(false); int64 N; cin >> N; vector V(N),T(N); for(int i=0;i> T[i] >> V[i]; DisjointSparseTable> S(T); // V_{0,0},...,V_{0,T1-1},V_{1,0},...,V_{1,T2-1},...,V_{N-1,TN-1} とする // T_iの区間和をS[l,r)とする // V_{i,0} に関して // 係数が1になるときを考えると、右側にT_{i}+T_{i+1}+...+T_{N-1} = T_i + S[i+1,N) 通り存在するので // 1 * V_{i,0} * (T_i + S[i+1,N)) // 係数が2になるときを考えると、 // 2 * V_{i,0} * (T_i + S[i+1,N)) // 一般のkに対して // k * V_{i,0} * (T_i + S[i+1,N)) // ここでkは 1,2,...,S[0,i)+1の範囲を動くので、 // V_{i,0}にかかる係数込みの数f(i,0)を考えると // f(i,0) = (S[0,i)+1)*(S[0,i)+2)/2 * V_{i,0} * (T_i + S[i+1,N)) // ここでf(i,j)に関して考えると // f(i,j) = Σ k * V_{i,j} * Σ 1 // ここで、i,jを固定したとき、右側のシグマ(Σ 1)に関しては、T_{i}-j + S[i+1,N) となるので // f(i,j) = Σ k * V_{i,j} * (T_{i}-j + S[i+1,N)) // ここで、kは 1,2,...,S[0,i)+(j+1) の範囲を動くので、 // f(i,j) = (S[0,i)+(j+1))*(S[0,i)+(j+1)+1)/2 * V_{i,j} * (T_{i}-j + S[i+1,N)) // ここで、iに関して、V_{i,j}が定数V_iであることをふまえて、jに関して降べきの順になおすと // f(i,j) = (j+S[0,i)+1) * (j+S[0,i)+2) / 2 * V_i * (-j + T_{i}+S[i+1,N)) // f(i,j) = (j+S[0,i)+1) * (j+S[0,i)+2) * (j - T_{i}-S[i+1,N)) *(-1) / 2 * V_i // f(i,j) = (j+a) * (j+b) * (j + c) * d // f(i,j) = (j*j*j + (a+b+c)*j*j + (ab+bc+ca)*j + abc)*d // ここでjを0からT_{i}-1までΣを取る計算がO(1)でできるようになる。 // あとはこれをi=1,...,Nに関して計算する // 最終的な答えは ans = ΣΣf(i,j)である modint ans = 0; for(int i=0;i