import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines import numpy as np N = int(readline()) ABC = np.array(read().split(),np.int64) A = ABC[::3] B = ABC[1::3] C = ABC[2::3] MOD = 1 << 20 # 二項係数 mod MODが必要。素因数 2 を無視して階乗を作る def cumprod(A, MOD = MOD): L = len(A); Lsq = int(L**.5+1) A = np.resize(A, Lsq**2).reshape(Lsq,Lsq) for n in range(1,Lsq): A[:,n] *= A[:,n-1]; A[:,n] %= MOD for n in range(1,Lsq): A[n] *= A[n-1,-1]; A[n] %= MOD return A.ravel()[:L] U = 1 << 22 x = np.arange(U, dtype = np.int64); x[0] = 1 n = 2 while n < U: x[n::n] //= 2 n *= 2 fact = cumprod(x, MOD) y = np.empty_like(x); y[1:] = x[1:][::-1] y[0] = pow(int(fact[-1]), MOD-1, MOD) # inverse fact_inv = cumprod(y, MOD)[::-1] def popcount_table(N): # N 未満の~~ L = (N-1).bit_length() A = np.zeros(1<