#include <bits/stdc++.h>
#define int int64_t
#define double long double
#define INIT std::ios_base::sync_with_stdio(0);std::cin.tie(0);std::cout<<std::fixed<<std::setprecision(15);DEFALLTYPE(VDEF)DEFALLTYPE(PDEF3)
const int MOD=1e9+7;
using namespace std;const int MAX=std::numeric_limits<int>::max();const int MIN=std::numeric_limits<int>::min();const double EPS=1e-7;
#define fou(i,a,n) for(int i=a;i<n;i++)
#define fod(i,a,n) for(int i=n-1;i>=a;i--)
#define tra(e,v) for(auto&e:v)
#define elif(c) else if(c)
#define fi first
#define se second
#define fir fi
#define sec se.fi
#define thi se.se
#define firs fi
#define seco sec
#define thir thi.fi
#define four thi.se
#define DEFALLTYPE(XDEF) XDEF(int,I)XDEF(double,D)XDEF(char,C)XDEF(String,S)XDEF(bool,B)XDEF(Modulo,M)
#define VDEF(t,T) typedef Vector<t>V##T;typedef Vector<V##T>VV##T;typedef Vector<VV##T>VVV##T;
#define PDEF(x,X,y,Y,z,Z,w,W) typedef std::pair<x,y>P##X##Y;VDEF(P##X##Y,P##X##Y)typedef std::pair<x,std::pair<y,z>>P##X##Y##Z;VDEF(P##X##Y##Z,P##X##Y##Z)typedef std::pair<x,std::pair<y,std::pair<z,w>>>P##X##Y##Z##W;VDEF(P##X##Y##Z##W,P##X##Y##Z##W)
#define PDEF1(y,Y,z,Z,w,W) PDEF(int,I,y,Y,z,Z,w,W)PDEF(double,D,y,Y,z,Z,w,W)PDEF(char,C,y,Y,z,Z,w,W)PDEF(String,S,y,Y,z,Z,w,W)PDEF(bool,B,y,Y,z,Z,w,W)PDEF(Modulo,M,y,Y,z,Z,w,W)
#define PDEF2(z,Z,w,W) PDEF1(int,I,z,Z,w,W)PDEF1(double,D,z,Z,w,W)PDEF1(char,C,z,Z,w,W)PDEF1(String,S,z,Z,w,W)PDEF1(bool,B,z,Z,w,W)PDEF1(Modulo,M,z,Z,w,W)
#define PDEF3(w,W) PDEF2(int,I,w,W)PDEF2(double,D,w,W)PDEF2(char,C,w,W)PDEF2(String,S,w,W)PDEF2(bool,B,w,W)PDEF2(Modulo,M,w,W)

// in, out
#define in(T,...) T __VA_ARGS__;_in(__VA_ARGS__)
void _in(){}template<typename Hd,typename...Tl>void _in(Hd&hd,Tl&&...tl){std::cin>>hd;_in(std::forward<Tl>(tl)...);}void out(){std::cout<<'\n';}template<typename T>void out(const T&a){std::cout<<a<<'\n';}template<typename Hd,typename ...Tl>void out(const Hd&hd,const Tl&...tl){std::cout<<hd<<' ';out(tl...);}

// std::pair io,calc
#define PairCalc(OP) template<typename T,typename U,typename V,typename W>std::pair<T,U>operator OP(const std::pair<T,U>&l,const std::pair<V,W>&r){return std::make_pair(l.first OP r.first,l.second OP r.second);}template<typename T,typename U,typename V,typename W>std::pair<T,U>operator OP##=(std::pair<T,U>&l,const std::pair<V,W>&r){return l=l OP r;}
template<typename T,typename U>std::istream&operator>>(std::istream&i,std::pair<T,U>&p){i>>p.first>>p.second;return i;}template<typename T,typename U>std::ostream&operator<<(std::ostream&o,const std::pair<T,U>&p){return o<<p.first<<' '<<p.second;}PairCalc(+)PairCalc(-)PairCalc(*)PairCalc(/)PairCalc(%)PairCalc(<<)PairCalc(>>)PairCalc(&)PairCalc(|)PairCalc(^)template<typename T,typename U>std::pair<T,U>mp(const T&t,const U&u){return std::make_pair(t,u);}template<typename T,typename U,typename V>std::pair<T,std::pair<U,V>>mp(const T&t,const U&u,const V&v){return std::make_pair(t,std::make_pair(u,v));}template<typename T,typename U,typename V,typename W>std::pair<T,std::pair<U,std::pair<V,W>>>mp(const T&t,const U&u,const V&v,const W&w){return std::make_pair(t,std::make_pair(u,std::make_pair(v,w)));}

// Slice class, Vector class
struct Slice{int first=0;int last=-1;int step=1;Slice(int f,int l=-1,int s=1):first(f),last(l),step(s){}Slice(std::initializer_list<int>l){if(l.size()!=3)return;first=*l.begin();last=*(l.begin()+1);step=*(l.begin()+2);}};
#define VecCalc(OP) Vector<T>operator OP(const Vector<T>&r)const{Vector<T>v(std::min(size(),r.size()));for(int i=0;i<v.size();i++)v[i]=value[i]OP r[i];return v;}Vector<T>operator OP(const T&r)const{Vector<T>v(size());for(int i=0;i<size();i++)v[i]=value[i]OP r;return v;}Vector<T>operator OP##=(const Vector<T>&r){return *this=*this OP r;}Vector<T>operator OP##=(const T&r){return *this=*this OP r;}
#define VecComp(OP) Vector<int>operator OP(const Vector<T>&r)const{Vector<int>v(std::min(size(),r.size()));for(int i=0;i<v.size();i++)v[i]=value[i]OP r[i];return v;}Vector<int>operator OP(const T&r)const{Vector<int>v(size());for(int i=0;i<size();i++)v[i]=value[i]OP r;return v;}
#define VVCalc(OP) template<typename T,typename U>Vector<Vector<T>>operator OP(Vector<Vector<T>>l,const U&r){for(Vector<T>&e:l)e OP##=r;return l;}template<typename T,typename U>Vector<Vector<T>>operator OP##=(Vector<Vector<T>>&l,const U&r){return l=l OP r;}
#define VVComp(OP) template<typename T,typename U>Vector<Vector<int>>operator OP(const Vector<Vector<T>>&l,const U&r){Vector<Vector<int>>v(l.size());for(int i=0;i<l.size();i++)v[i]=l[i] OP r;return v;}
template<typename T>class Vector{std::vector<T>value;public:Vector(int s=0,T v=T()){if(s>=0)assign(s,v);else{assign(-s,v);for(T&e:value)std::cin>>e;}}Vector(const std::initializer_list<T>&l){value=std::vector<T>{l};}template<typename U>Vector(const Vector<U>&v){resize(v.size());for(int i=0;i<size();i++)value[i]=v[i];}Vector(const std::vector<T>&v){value=v;}int size()const{return value.size();}T operator[](int i)const{return value[i];}T&operator[](int i){return value[i];}Vector<T>operator[](Slice s)const{s.last=(s.last<0?s.last+size()+1:s.last);Vector<T>v;for(int i=s.first;i<s.last;i+=s.step)v.pub(value[i]);return v;}Vector<T>&operator=(const Vector<T>&v){resize(v.size());for(int i=0;i<size();i++)value[i]=v[i];return *this;}Vector<T>operator+()const{return *this;}Vector<T>operator-()const{Vector<T>v(value.size());for(int i=0;i<size();i++)v[i]=-value[i];return v;}Vector<T>operator++(){for(T&e:value)e++;return *this;}Vector<T>operator--(){for(T&e:value)e--;return *this;}Vector<T>operator++(int32_t){Vector<T>v=*this;for(T&e:value)e++;return v;}Vector<T>operator--(int32_t){Vector<T>v=*this;for(T&e:value)e--;return v;}std::vector<T>stdVector()const{return value;}std::vector<T>&stdVector(){return value;}void out(){for(const T&e:value)std::cout<<e<<'\n';}void iota(){for(int i=0;i<size();i++)value[i]=i;}
T last()const{return value[size()-1];}T&last(){return value[size()-1];}auto begin(){return value.begin();}auto end(){return value.end();}auto begin()const{return value.begin();}auto end()const{return value.end();}T sum(int l=0,int r=-1)const{T v=T();r=(r<0?size():r);for(int i=l;i<r;i++)v+=value[i];return v;}int argmin()const{return std::min_element(begin(),end())-begin();}int argmax()const{return std::max_element(begin(),end())-begin();}T min()const{return value[argmin()];}T max()const{return value[argmax()];}T dot(const Vector<T>&v)const{T r=T();for(int i=0;i<std::min(size(),v.size());i++)r+=value[i]*v[i];return r;}void resize(int s,T v=T()){value.resize(s,v);}void assign(int s,const T&v){value.assign(s,v);}void pub(const T&v){value.push_back(v);}void pub(const Vector<T>&v){value.insert(end(),v.begin(),v.end());}void insert(int i,const T&v){value.insert(begin()+i,v);}void insert(int i,const Vector<T>&v){value.insert(begin()+i,v.begin(),v.end());}void pob(){value.pop_back();}void erase(int i,int j=-1){if(j<0)value.erase(begin()+i);else value.erase(begin()+i,begin()+j);}void erase_unique(){value.erase(std::unique(begin(),end()),end());}void reverse(){std::reverse(begin(),end());}void rotatedown(int i){if(i>0)std::rotate(begin(),begin()+i,end());}void rotateup(int i){if(i>0)std::rotate(value.rbegin(),value.rbegin()+i,value.rend());}
void sortup(){std::sort(begin(),end());}void sortdown(){std::sort(value.rbegin(),value.rend());}void cumsum(){for(int i=0;i<size()-1;i++)value[i+1]+=value[i];}void diff(){for(int i=size()-2;i>=0;i--)value[i+1]-=value[i];}T cumpart(int l,int r)const{return value[r-1]-(l=0?0:value[l-1]);}void bucketsortup(){int m=min();Vector<int>b(max()-m+1);for(int e:value)b[e-m]++;b.cumsum();for(int i=0;i<b.size();i++)for(int j=(i==0?0:b[i-1]);j<b[i];j++)value[j]=m+i;}void bucketsortdown(){bucketsortup();reverse();}void compress(){Vector<T>u(value);u.sortup();u.erase_unique();std::unordered_map<T,int>m;for(int i=0;i<u.size();i++)m[u[i]]=i;for(int i=0;i<size();i++)value[i]=m[value[i]];}void argofsortup(){Vector<std::pair<T,T>>p(size());for(int i=0;i<size();i++)p[i]=std::make_pair(value[i],i);p.sortup();for(int i=0;i<size();i++)value[i]=p[i].second;}void argofsortdown(){Vector<std::pair<T,T>>p(size());for(int i=0;i<size();i++)p[i]=std::make_pair(value[i],i);p.sortdown();for(int i=0;i<size();i++)value[i]=p[i].second;}int findover(const T&v){return std::upper_bound(begin(),end(),v)-begin();}int findunder(const T&v){return std::lower_bound(begin(),end(),v)-begin();}int count(const T&v){return findover(v)-findunder(v);}VecCalc(+)VecCalc(-)VecCalc(*)VecCalc(/)VecCalc(%)VecCalc(<<)VecCalc(>>)VecCalc(&)VecCalc(|)VecCalc(^)VecComp(==)VecComp(!=)VecComp(>=)VecComp(<=)VecComp(>)VecComp(<)};
VVCalc(+)VVCalc(-)VVCalc(*)VVCalc(/)VVCalc(%)VVCalc(<<)VVCalc(>>)VVCalc(&)VVCalc(|)VVCalc(^)VVComp(==)VVComp(!=)VVComp(>=)VVComp(<=)VVComp(>)VVComp(<)template<typename T,typename U>Vector<std::pair<T,U>>unite(const Vector<T>&v,const Vector<U>&u){int s=std::min(v.size(),u.size());Vector<std::pair<T,U>>r(s);for(int i=0;i<s;i++)r[i]=std::make_pair(v[i],u[i]);return r;}template<typename T,typename U>std::pair<Vector<T>,Vector<U>>separate(const Vector<std::pair<T,U>>&p){Vector<T>v(p.size());Vector<U>u(p.size());for(int i=0;i<p.size();i++){v[i]=p[i].first;u[i]=p[i].second;}return std::make_pair(v,u);}template<typename T>std::istream&operator>>(std::istream&i,Vector<T>&v){for(T&e:v)i>>e;return i;}template<typename T>std::ostream&operator<<(std::ostream&o,const Vector<T>&v){if(v.size()==0)return o;for(int i=0;i<v.size()-1;i++)o<<v[i]<<' ';return o<<v.last();}Vector<int>baseVector(int n,int b){Vector<int>v(64);for(int&e:v){e=n%b;n/=b;}return v;}int baseVectorValue(Vector<int>v,int b){int n=0,m=1;for(int&e:v){n+=e*m;m*=b;}return n;}

// Matrix class need Vector class
#define MatCalc(OP) Matrix<T>operator OP(const Matrix<T>&r)const{Matrix<T>v(std::min(size(),r.size()));for(int i=0;i<v.size();i++)v[i]=value[i]OP r[i];return v;}Matrix<T>operator OP(const Vector<T>&r)const{Matrix<T>v(std::min(size(),r.size()));for(int i=0;i<size();i++)v[i]=value[i]OP r;return v;}Matrix<T>operator OP(const T&r)const{Matrix<T>v(size());for(int i=0;i<size();i++)v[i]=value[i]OP r;return v;}Matrix<T>operator OP##=(const Matrix<T>&r){return *this=*this OP r;}Matrix<T>operator OP##=(const Vector<T>&r){return *this=*this OP r;}Matrix<T>operator OP##=(const T&r){return *this=*this OP r;}
#define MatComp(OP) Matrix<int>operator OP(const Matrix<T>&r)const{Matrix<int>v(std::min(size(),r.size()));for(int i=0;i<v.size();i++)v[i]=value[i]OP r[i];return v;}Matrix<int>operator OP(const Vector<T>&r)const{Matrix<int>v(size());for(int i=0;i<size();i++)v[i]=value[i]OP r;return v;}Matrix<int>operator OP(const T&r)const{Matrix<int>v(size());for(int i=0;i<size();i++)v[i]=value[i]OP r;return v;}
template<typename T>class Matrix{Vector<Vector<T>>value;public:Matrix(int c=0,int r=0,T v=T()){if(c>=0&&r>=0)assign(c,r,v);else{assign(-c,-r,v);for(Vector<T>&e:value)std::cin>>e;}}Matrix(std::pair<int,int>p,T v=T()){if(p.first>=0&&p.second>=0)assign(p.first,p.second,v);else{resize(-p.first,-p.second);for(Vector<T>&e:value)std::cin>>e;}}Matrix(const std::initializer_list<std::initializer_list<T>>&l){value.resize(l.size());for(int i=0;i<size();i++)value[i]=*(l.begin()+i);rect();}template<typename U>Matrix(const Matrix<U>&v){resize(v.size());for(int i=0;i<size();i++)value[i]=v[i];}Matrix(const Vector<Vector<T>>&v){value.resize(v.size());for(int i=0;i<size();i++)value[i]=v[i];rect();}Matrix(const std::vector<std::vector<T>>&v){value.resize(v.size());for(int i=0;i<size();i++)value[i]=v[i];rect();}void rect(){Vector<T>v(size());for(int i=0;i<size();i++)v[i]=value[i].size();resize(size(),v.max());}
int size()const{return value.size();}std::pair<int,int>shape()const{return std::make_pair(size(),size()==0?0:value[0].size());}Vector<T>operator[](int i)const{return value[i];}Vector<T>&operator[](int i){return value[i];}T operator[](std::pair<int,int>p)const{return value[p.first][p.second];}T&operator[](std::pair<int,int>p){return value[p.first][p.second];}Matrix<T>operator[](Slice p)const{return value[p];}Matrix<T>operator[](std::pair<Slice,Slice>p)const{p.first.last=(p.first.last<0?p.first.last+shape().first+1:p.first.last);p.second.last=(p.second.last<0?p.second.last+shape().second+1:p.second.last);Matrix<T>v;for(int i=p.first.first;i<p.first.last;i+=p.first.step){Vector<T>u;for(int j=p.second.first;j<p.second.last;j+=p.second.step)u.pub(value[i][j]);v.vstack(u);}return v;}Matrix<T>&operator=(const Matrix<T>&v){value.resize(size());for(int i=0;i<v.size();i++)value[i]=v[i];return *this;}Matrix<T>operator+()const{return *this;}Matrix<T>operator-()const{Matrix<T>v(value.size());for(int i=0;i<size();i++)v[i]=-value[i];return v;}Matrix<T>operator++(){for(Vector<T>&e:value)e++;return *this;}Matrix<T>operator--(){for(Vector<T>&e:value)e--;return *this;}Matrix<T>operator++(int32_t){Matrix<T>v=*this;for(Vector<T>&e:value)e++;return v;}Matrix<T>operator--(int32_t){Matrix<T>v=*this;for(Vector<T>&e:value)e--;return v;}std::vector<std::vector<T>>stdVector(){std::vector<std::vector<T>>v(size());for(int i=0;i<size();i++)v[i]=value[i].stdVector();return v;}void out(){for(const Vector<T>&e:value)std::cout<<e<<'\n';}Vector<Vector<T>>vectorVector(){return value;}Vector<T>last()const{return value[size()-1];}
Vector<T>&last(){return value[size()-1];}Vector<T>vector()const{Vector<T>v;for(const Vector<T>&e:value)v.pub(e);return v;}auto begin(){return value.begin();}auto end(){return value.end();}auto begin()const{return value.begin();}auto end()const{return value.end();}T sum(int cl=0,int rl=0,int cr=-1,int rr=-1)const{T v=T();cr=(cr<0?size():cr);for(int i=cl;i<cr;i++)v+=value[i].sum(rl,rr);return v;}std::pair<int,int>argmin()const{Vector<int>v(size());for(int i=0;i<size();i++)v[i]=value[i].min();int m=v.argmin();return std::make_pair(m,value[m].argmin());}std::pair<int,int>argmax()const{Vector<int>v(size());for(int i=0;i<size();i++)v[i]=value[i].max();int m=v.argmax();return std::make_pair(m,value[m].argmax());}T min()const{Vector<int>v(size());for(int i=0;i<size();i++)v[i]=value[i].min();return v.min();}T max()const{Vector<int>v(size());for(int i=0;i<size();i++)v[i]=value[i].max();return v.max();}void dot(Matrix<T>v){Matrix<T>m(value);assign(shape().first,v.shape().second,0);for(int i=0;i<shape().first;i++)for(int j=0;j<shape().second;j++)for(int k=0;k<std::min(m.shape().second,v.shape().first);k++)value[i][j]+=m[i][k]*v[k][j];}void resize(int c,Vector<T>v=Vector<T>()){value.resize(c,v);}void resize(int c,int r,T v=T()){resize(c);for(Vector<T>&e:value)e.resize(r,v);}void resize(std::pair<int,int>p,T v=T()){resize(p.first,p.second,v);}void assign(int c,const Vector<T>&v){value.assign(c,v);}void assign(int c,int r,T v){assign(c,Vector<T>(r,v));}void assign(std::pair<int,int>p,const T&v){assign(p.first,p.second,v);}
void vstack(const Vector<T>&v){if(shape().second<v.size()&&size()>0){value.pub(v[{0,shape().second,1}]);}else{value.pub(v);value.last().resize(shape().second);}}void vstack(const Matrix<T>&v){Matrix<T>u(v[{{0,-1,1},{0,std::min(shape().second,v.shape().second),1}}]);for(const Vector<T>&e:u)vstack(e);}void hstack(const Vector<T>&v){if(size()==0)resize(v.size());for(int i=0;i<std::min(size(),v.size());i++)value[i].pub(v[i]);resize(shape());}void hstack(const Matrix<T>&v){if(size()==0)resize(v.size());for(int i=0;i<std::min(size(),v.size());i++)value[i].pub(v[i]);resize(shape());}void vpob(){value.pob();}void hpob(){for(Vector<T>&e:value)e.pob();}void verase(int i,int j=-1){if(j==-1)value.erase(i);else value.erase(i,j);}void herase(int i,int j=-1){for(Vector<T>&e:value)if(j==-1)e.erase(i);else e.erase(i,j);}void vinsert(int i,const Vector<T>&v){if(shape()==std::make_pair(int(0),int(0)))vstack(v);else value.insert(i,v[{0,shape().second,1}]);}void vinsert(int i,const Matrix<T>&v){if(shape()==std::make_pair(int(0),int(0)))vstack(v);else value.insert(i,v[{{0,-1,1},{0,std::min(shape().second,v.shape().second),1}}].vectorVector());}void hinsert(int i,const Vector<T>&v){if(shape()==std::make_pair(int(0),int(0)))hstack(v);else for(int j=0;j<std::min(size(),v.size());j++)value[j].insert(i,v[j]);for(int j=std::min(size(),v.size());j<size();j++)value[j].insert(i,0);}void hinsert(int i,const Matrix<T>&v){if(shape()==std::make_pair(int(0),int(0)))hstack(v);else for(int j=0;j<std::min(size(),v.size());j++)value[j].insert(i,v[j]);for(int j=std::min(size(),v.size());j<size();j++)value[j].resize(v.shape().second);}
void transpose(){std::pair<int,int>s=shape();if(s.first<s.second)for(int i=0;i<s.second-s.first;i++)value.pub(Vector<T>(s.first));else for(int i=0;i<s.second;i++)value[i].resize(s.first);for(int i=0;i<std::min(s.first,s.second);i++)for(int j=i+1;j<size();j++)std::swap(value[i][j],value[j][i]);resize(s.second,s.first);}void power(int n){Matrix<T>m(*this);assign(size(),size(),0);for(int i=0;i<size();i++)value[i][i]=1;while(n>0){if(n&1)dot(m);m.dot(m);n/=2;}}void cumsum(){value.cumsum();for(Vector<T>&e:value)e.cumsum();}T cumpart(int cl,int rl,int cr,int rr)const{return value[cr-1][rr-1]-(cl==0?0:value[cl-1][rr-1])-(rl==0?0:value[cr-1][rl-1])+((cl==0||rl==0)?0:value[cl-1][rl-1]);}void diff(){value.diff();for(Vector<T>&e:value)e.diff();}void compress(){Vector<T>u=vector();u.sortup();u.erase_unique();std::unordered_map<T,int>m;for(int i=0;i<u.size();i++)m[u[i]]=i;for(int i=0;i<shape().first;i++)for(int j=0;j<shape().second;j++)value[i][j]=m[value[i][j]];}MatCalc(+)MatCalc(-)MatCalc(*)MatCalc(/)MatCalc(%)MatCalc(<<)MatCalc(>>)MatCalc(&)MatCalc(|)MatCalc(^)MatComp(==)MatComp(!=)MatComp(>=)MatComp(<=)MatComp(>)MatComp(<)};

// String class need Vector class
#define DefOtherType(RTYPE,OP,CONST) RTYPE operator OP(const char*s)CONST{return operator OP(String(s));}RTYPE operator OP(const std::string&s)CONST{return operator OP(String(s));}RTYPE operator OP(char c)CONST{return operator OP(String(c));}
#define StrComp(OP) bool operator OP(const String&s)const{return str OP s.stdString();}DefOtherType(bool,OP,const)
class String:public std::string{std::string str;public:String(){}String(const char*s):str(s){}String(char s):str(1,s){}String(int i,char c){str=std::string(i,c);}String(int32_t i):str(std::to_string(i)){}String(int64_t i):str(std::to_string(i)){}String(const std::string&s):str(s){}char operator[](int i)const{return str[i];}char&operator[](int i){return str[i];}String operator[](Slice s)const{s.last=(s.last<0?s.last+size()+1:s.last);String r;for(int i=s.first;i<s.last;i+=s.step)r.pub(str[i]);return r;}void operator--(int32_t){pob();}String&operator=(const String&s){str=s.stdString();return *this;}DefOtherType(String&,=,)String&operator<<(const String&s){pub(s);return *this;}DefOtherType(String&,<<,)String operator+(const String&s)const{String r(*this);r.pub(s);return r;}DefOtherType(String,+,const)String operator+=(const String&s){pub(s);return *this;}DefOtherType(String,+=,)StrComp(==)StrComp(!=)StrComp(>=)StrComp(<=)StrComp(>)StrComp(<)std::string stdString()const{return str;}std::string&stdString(){return str;}char last()const{return str[size()-1];}Vector<char>toVector()const{Vector<char>v;for(char c:str)v.pub(c);return v;}char&last(){return str[size()-1];}auto begin(){return str.begin();}auto end(){return str.end();}auto begin()const{return str.begin();}auto end()const{return str.end();}
int size()const{return str.size();}String substr(int p,int s=-1)const{return operator[]({p,s<0?s:p+s,1});}int32_t toInt(){return std::stoi(str);}int64_t toLong(){return std::stol(str);}Vector<int>find(const String&s)const{Vector<int>v;auto i=str.find(s.stdString());while(i!=std::string::npos){v.pub(i);i=str.find(s.stdString(),i+s.size());}return v;}Vector<int>find_dup(const String&s)const{Vector<int>v;auto i=str.find(s.stdString());while(i!=std::string::npos){v.pub(i);i=str.find(s.stdString(),i+1);}return v;}void resize(int i,char c=0){str.resize(i,c);}void assign(int i,char c){str.assign(i,c);}void pub(const String&s){str+=s.stdString();}void pob(){str.pop_back();}void reverse(){std::reverse(begin(),end());}void insert(int i,const String&s){str.insert(i,s.stdString());}void erase(int i,int j=-1){if(j<0)str.erase(i,i+1);else str.erase(i,j-i);}void erase_unique(){str.erase(std::unique(begin(),end()),end());}void rotatedown(int i){std::rotate(begin(),begin()+i,end());}void rotateup(int i){std::rotate(str.rbegin(),str.rbegin()+i,str.rend());}void sortup(){int m=*std::min_element(begin(),end());int M=*std::max_element(begin(),end());Vector<char>b(M-m+1);for(char e:str)b[e-m]++;b.cumsum();for(int i=0;i<b.size();i++)for(int j=(i==0?0:b[i-1]);j<b[i];j++)str[j]=m+i;}void sortdown(){sortup();reverse();}};std::istream&operator>>(std::istream&i,String&s){i>>s.stdString();return i;}std::ostream&operator<<(std::ostream&o,const String&s){return o<<s.stdString();}

// Modulo class
#define ModCalc(OP) Modulo operator OP(const Modulo&l,const Modulo&r){return Modulo(l.val()OP r.val());}Modulo operator OP(const Modulo&l,const int64_t&r){return Modulo(l.val()OP Modulo(r));}int64_t operator OP(const int64_t&l,const Modulo&r){return l OP r.val();}Modulo operator OP##=(Modulo&l,const Modulo&r){return l=l OP r;}Modulo operator OP##=(Modulo&l,const int64_t&r){return l=l OP r;}int64_t operator OP##=(int64_t&l,const Modulo&r){return l=l OP r;}
#define ModComp(OP) bool operator OP(const Modulo&l,const Modulo&r){return l.val()OP r.val();}bool operator OP(const Modulo&l,const int64_t&r){return l.val()OP r;}bool operator OP(const int64_t&l,const Modulo&r){return l OP r.val();}
class Modulo{int64_t value;public:Modulo():value(0){}Modulo(const int64_t&v){value=v;normalize();}void normalize(){value=(value%mod()+mod())%mod();}Modulo(const Modulo&m):value(m.val()){}Modulo inv()const{int64_t a=value;int64_t b=mod(),u=0,v=1;while(a>1){u-=b/a*v;b%=a;std::swap(a,b);std::swap(u,v);}return Modulo(v);}int64_t val()const{return value;}int64_t&val(){return value;}Modulo&operator=(const Modulo&m){value=m.val();return *this;}int64_t mod()const{return MOD;}Modulo&operator=(const int64_t&v){value=v;return *this;}Modulo operator++(){return Modulo(++value);}Modulo operator--(){return Modulo(--value);}Modulo operator++(int32_t){return Modulo(value++);}Modulo operator--(int32_t){return Modulo(value--);}Modulo operator+()const{return *this;}Modulo operator-()const{return Modulo(-value);}Modulo power(int64_t i)const{int64_t x=value;int64_t r=1;while(i>0){if(i&1)r=r*x%mod();x=x*x%mod();i/=2;}return Modulo(r);}};std::ostream&operator<<(std::ostream&o,const Modulo&m){return o<<m.val();}std::istream&operator>>(std::istream&i,Modulo&m){i>>m.val();m.normalize();return i;}ModCalc(+)ModCalc(-)ModCalc(*)ModCalc(<<)ModCalc(>>)ModCalc(&)ModCalc(|)ModCalc(^)ModComp(==)ModComp(!=)ModComp(>=)ModComp(<=)ModComp(>)ModComp(<)Modulo operator/(const Modulo&l,const Modulo&r){return Modulo(l.val()*r.inv());}Modulo operator/(const Modulo&l,const int64_t&r){return Modulo(l.val()*Modulo(r).inv());}Modulo operator/(const int64_t&l,const Modulo&r){return Modulo(Modulo(l)*r.inv());}

// FFT, NNT need Vector Modulo class
std::unordered_map<int,int>MOD_ROOT={{1224736769,3},{1053818881,7},{1051721729,6},{1045430273,3},{1012924417,5},{1007681537,3},{1004535809,3},{998244353,3},{985661441,3},{976224257,3},{975175681,17},{962592769,7},{950009857,7},{943718401,7},{935329793,3},{924844033,5},{469762049,3},{167772161,3}};Vector<std::complex<double>>fft(Vector<std::complex<double>>a,bool inverse=false){int n=a.size(),h=std::log2(n);for(int i=0;i<n;i++){int j=0;for(int k=0;k<h;k++)j|=(i>>k&1)<<(h-1-k);if(i<j)std::swap(a[i],a[j]);}for(int b=1;b<n;b*=2){for(int j=0;j<b;j++){std::complex<double>w=std::polar(1.0,(2*M_PI)/(2*b)*j*(inverse?1:-1));for(int k=0;k<n;k+=b*2){std::complex<double>s=a[j+k],t=a[j+k+b]*w;a[j+k]=s+t;a[j+k+b]=s-t;}}}a/=std::complex<double>(inverse?n:1);return a;}Vector<Modulo>ntt(Vector<Modulo>a,bool inverse=false){int n=a.size(),h=std::log2(n);Modulo root=MOD_ROOT[MOD];for(int i=0;i<n;i++){int j=0;for(int k=0;k<h;k++)j|=(i>>k&1)<<(h-1-k);if(i<j)std::swap(a[i],a[j]);}for(int b=1;b<n;b*=2){Modulo w=root.power((a[0].mod()-1)/(b*2));if(inverse)w=w.inv();for(int j=0;j<n;j+=b*2){Modulo wn=1;for(int k=0;k<b;k++){Modulo s=a[j+k+0],t=a[j+k+b]*wn;a[j+k]=s+t;a[j+k+b]=s-t;wn=wn*w;}}}if(inverse){Modulo v=Modulo(n).inv();a*=v;}return a;}
Vector<double>convolve(Vector<double>a,Vector<double>b){if(a.size()==0||b.size()==0)return Vector<double>();int s=a.size()+b.size()-1,t=std::pow(2,std::ceil(std::log2(s)));a.resize(t);b.resize(t);Vector<std::complex<double>>A=fft(a),B=fft(b);A*=B;A=fft(A,true);a.resize(s);for(int i=0;i<s;i++)a[i]=A[i].real();return a;}Vector<int>convolve(Vector<int>a,Vector<int>b){return convolve(Vector<double>(a),Vector<double>(b))+0.5;}Vector<Modulo>convolve(Vector<Modulo>a,Vector<Modulo>b){if(a.size()==0||b.size()==0)return Vector<Modulo>();int s=a.size()+b.size()-1,t=std::pow(2,std::ceil(std::log2(s)));a.resize(t);b.resize(t);Vector<Modulo>A=ntt(a),B=ntt(b);A*=B;a=ntt(A,true);a.resize(s);return a;}

// math function
template<typename T>T sign(const T&x){return(x>0)-(x<0);}template<typename T>T abs(const T&x){return x*sign(x);}template<typename T>T power(T x,int y){T r=x*0+1;while(y>0){if(y&1)r*=x;x*=x;y/=2;}return r;}int _gcd(const int&a,const int&b){return b?_gcd(b,a%b):a;}int gcd(const int&a,const int&b){return _gcd(std::max(a,b),std::min(a,b));}int lcm(const int&a,const int&b){return a/gcd(a,b)*b;}






int32_t main(){INIT;
  in(int,n);
  VI a(-n);
  VVI b(n);
  fou(i,0,n){
    b[i]=baseVector(a[i],2);
  }

  VI c0=baseVector(0,2);
  VI c1=baseVector(0,2);
  fou(i,0,n){
    c0+=-b[i]+1;
    c1+=b[i];
  }
  VI c=c0*c1;

  Modulo ans=0;
  Modulo m=1;
  tra(e,c){
    ans+=e*m;
    m*=2;
  }


  out(ans);


  

  
}