/**-------------------------快速幂-------------------------*/
///快速幂取余，O(logb)，底数越大速度慢的越快
const int mod = 1e9+7;
ll quick_pow(ll a,ll b){
ll ans = 1;
while(b){
if(b&1) ans = (ans * a)%mod;
b>>=1;
a = (a * a)%mod;
}
return ans;
}
///矩阵快速幂取余，O(mnlogb)
const int mod = 1e9+7;
struct matrix{
static const ll maxn = 4;
ll mat[maxn][maxn];
ll n,m;
matrix(ll _n = maxn,ll _m = maxn):n(_n),m(_m){memset(mat,0,sizeof(mat));}//初始化n阶零矩阵
void I(){for(int i = 0;i>=1;
a = a * a;
}
return ans;
}
/**-------------------------素数判断-------------------------*/
///试除法，O(n^1/2)，若是合数，那么在[1,sqrt(n)]中至少有一个质因子
bool isPrime_naive(int n){
if(n == 2) return 1;
if(n == 1) return 0;
for(int i = 2;i*i<=n;i++) if(!(n%i)) return 0;
return 1;
}
///kn+i法，k=30，O(n^2/15)，kn+i中的i = 1,7,11,13,17,19,23,29时，kn+i的值才可能成为待判数字的质因子
bool isPrime_kni(int n){
if(n == 2 || n == 3 || n == 5) return 1;
if(n == 1 || !(n%2) || !(n%3) || !(n%5)) return 0;
ll a[8] = {4,2,4,2,4,6,2,4},p = 0;//下一个数字的增量
for(int i = 7;i*i<=n;i+=a[p++],p%=8) if(!(n%i)) return 0;
return 1;
}
///预处理法，对于多组数据，如果n是合数就一定有在[1,n^1/2]的质因子，先预处理出[1,n^1/2]的所有素数,然后对n测试
/**-------------------------素数筛-------------------------*/
///埃氏筛，O(nloglogn)，通过标记素数的倍数筛掉合数
const int N = 1e6+7;
bool vis[N];
int prime[N],cnt;
void eratosthenes_screen(int n){
for(int i = 2;i<=n;i++){
if(vis[i]) continue;
prime[cnt++] = i;
for(int j = 2;j*i<=n;j++) vis[i*j] = 1;
}
}
///欧拉筛(线性筛)，O(n)，每个合数只会被最小质因子筛掉
const int N = 1e6+7;
bool vis[N];
int prime[N],cnt;
void euler_screen(int n){
for(int i = 2;i<=n;i++){
if(!vis[i]) prime[cnt++] = i;
for(int j = 0;j> 1,b >> 1) << 1;//最后要把因子2乘上
else if(a&1 && !(b&1)) return stein_recursion(a,b >> 1);
else if(!(a&1) && b&1) return stein_recursion(a >> 1,b);
else return stein_recursion(a - b,b);
}
//迭代版
int stein_iteration(int a,int b){
int k = 1;
while(!(a&1) && !(b&1)) k<<=1,a>>=1,b>>=1;//k记录因子2乘积
while(!(a&1)) a>>=1;
while(!(b&1)) b>>=1;
if(a