#include #define rep(i, n) for (int i = 0; i < (int)(n); i++) using namespace std; using ll=long long; ll memo[1<<16]; const string yes="Yes",no="No"; const ll bip=1000000007; ll modinv(ll a,ll b){ if(abs(a)==1)return a; if(a<0)return modinv(a+b,b); ll x=modinv(-(b%a),a); return ((b*x+1)/a)%b; } ll modpow(ll a,ll b,ll c){ ll s=1,t=a; for(int i=0;i<64;i++){ if((b&(((ll)1)<>n; cout<<(n*(n+1))/2<