typedef long long ll; ll mul(ll a,ll b) { ll r; for(r=0;b;a=(a<<1)%M,b>>=1) if(b&1) r=(r+a)%M; return r; }
应该是(a*b)%M，a(2^i+...2^j)%M