#include #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; using lint=long long; inline int popcount(int x){ x=((x>>1)&0x55555555)+(x&0x55555555); x=((x>>2)&0x33333333)+(x&0x33333333); x=((x>>4)+x)&0x0f0f0f0f; x+=(x>>8); x+=(x>>16); return x&0x3f; } template T gcd(const T& a,const T& b){ return b==0?a:gcd(b,a%b); } template class rational{ T num,den; rational& reduce(){ T g=gcd(num,den); if(g<-1) g*=-1; if(g>1) num/=g, den/=g; return *this; } public: rational(const T& num=0){ *this=num; } rational(const T& num,const T& den):num(num),den(den){ if(den<0){ this->num*=-1; this->den*=-1; } reduce(); } const T& nume()const{ return num; } const T& deno()const{ return den; } rational& operator+=(const T& v){ num+=den*v; return reduce(); } rational& operator-=(const T& v){ num-=den*v; return reduce(); } rational& operator+=(const rational& r){ T g=gcd(den,r.den); den/=g; num*=r.den/g; num+=den*r.num; den*=r.den; return reduce(); } rational& operator-=(const rational& r){ T g=gcd(den,r.den); den/=g; num*=r.den/g; num-=den*r.num; den*=r.den; return reduce(); } rational& operator*=(const rational& r){ T g1=gcd(num,r.den),g2=gcd(den,r.num); num/=g1; num*=r.num/g2; den/=g2; den*=r.den/g1; if(den<0) num*=-1, den*=-1; return reduce(); } rational& operator/=(const rational& r){ T g1=gcd(num,r.num),g2=gcd(den,r.den); num/=g1; num*=r.den/g2; den/=g2; den*=r.num/g1; if(den<0) num*=-1, den*=-1; return reduce(); } rational operator+(const T& v)const{ return rational(*this)+=v; } rational operator-(const T& v)const{ return rational(*this)-=v; } rational operator+(const rational& r)const{ return rational(*this)+=r; } rational operator-(const rational& r)const{ return rational(*this)-=r; } rational operator*(const rational& r)const{ return rational(*this)*=r; } rational operator/(const rational& r)const{ return rational(*this)/=r; } bool operator< (const rational& r)const{ return num*r.den (const rational& r)const{ return r<(*this); } bool operator<=(const rational& r)const{ return !(r<(*this)); } bool operator>=(const rational& r)const{ return !((*this)> memo[1<<7]; inline void add(int S,const rational x){ rep(T,1<