#include<iostream>
using namespace std;
#define  ll long long
//快速幂
/*
    例如a^7   7=111=2^2*1+2^1*1+2^0*1=4+2+1
    a^7=a^4*a^2*a^1
    每次指数位置>>右移一位相当于指数位置除以2 
    对应于底数变成平方
    a->a^2->a^4
    res=1;        a      b:00000111 
    res=1*a=a;     a*a=a^2     b:00000011    
    res=a*a^2=a^1*a^2      a^2*a^2=a^4  b:00000001
    res=a^1*a^2*a^4=a^7   b:00000000
*/ 
ll quick_pow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1){
            res=res*a;
        }
        a=a*a;
    ...