1 LL pow1_sum(LL a,LL b,LL mod) //a*b%mod 2 { 3     a=a%mod; 4     b=b%mod; 5     LL cur=0; 6     while(b) 7     { 8         if(b&1) 9         {10             cur=cur+a;11             if(cur>=mod) cur=cur-mod;12         }13         a=a<<1;14         if(a>=mod) a=a-mod;15         b=b>>1;16     }17     return cur;18 }19 LL pow_sum(LL a,LL b,LL mod) //a^b%mod20 {21     LL cur= 1;22     a=a%mod;23     while(b)24     {25         if(b&1)26         {27             cur=(cur*b)%mod;28         }29         a=(a*a)%mod;30         b=b>>1;31     }32     return cur;33 }