1 const int mod = 1000; 2  3 int bitpow(int x, int n) { 4     int ans = 1; 5     int t = x; 6     while(n) { 7         if(n & 1) { 8             ans = (ans * t) % mod; 9         }10         t = t * t % mod;11         n >>= 1;12     }13     return ans;14 }15 16 int bitadd(int x, int y) {17     int xr = x ^ y;18     int nd = x & y;19     while(nd) {20         int xr1 = xr;21         int nd1 = nd << 1;22         xr = xr1 ^ nd1;23         nd = xr1 & nd1;24     }25     return xr;26 }27 28 int negtive(int x) {29     return bitadd(~x, 1);30 }31 32 int bitminus(int x, int y) {33     return bitadd(x, negtive(y));34 }35 36 int bitmulti(int x, int y) {37     int ans = 0;38     while(y) {39         if(y & 1) {40             ans = bitadd(ans, x);41         }42         x = (x << 1);43         y = (y >> 1);44     }45     return ans;46 }47 48 int bitdiv(int x, int y) {49     int ans = 0;50     for(int i = 31; i >= 0; i--) {51         if((x>>i) >= y) {52             ans += (1<