#include using namespace std; #define sd(mark) scanf("%d",&mark) #define ss(mark) scanf("%s",mark) #define sl(mark) scanf("%lld",&mark) #define debug(mark) printf("check%d\n",mark) #define clr(mark) memset(mark,0,sizeof(mark)) #define F first #define S second #define MP make_pair #define PB push_back #define ll long long #define N 100010 #define mod 1000000007 ll bit[N]; ll val[N]; ll K; ll c[N]; ll pow1(ll a,ll b) { if(b==0) return 1; ll ret=pow1(a,b/2); ret=(ret*ret)%mod; if(b&1) ret=(a*ret)%mod; return ret; } void update(int i,ll val) { while(i