# https://zhuanlan.zhihu.com/p/95902286 """ 重要的是2点： #####s1: a^n = (1) n是奇数， a^(n-1) x a (2) 偶数， (a^n/2) ^2 ######s2: 取模的公式： （aXb）mod c = (a mod c x b mod c)mod c """ times = int(input()) listall = [] def quickpow(a,b,p): if b == 0: return 1 if b%2==1: return quickpow(a, b-1,p) *a % p else: # 此步骤tmp...