mod

class Combination:
    def __init__(self, n_max=0, mod=-1):
        self.init(n_max, mod)
    def init(self, n_max, mod=1000000007):
        self.mod = mod
        if mod != -1:
            self.modinv = self.make_modinv_list(n_max)
            self.fac, self.facinv = self.make_factorial_list(n_max)
    def __call__(self, n, r):
        if self.mod == -1:
            return self.cmb(n, r)
        else:
            return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod
    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n + 1):
            fac.append(fac[i - 1] * i % self.mod)
            facinv.append(facinv[i - 1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n + 1)
        modinv[1] = 1
        for i in range(2, n + 1):
            modinv[i] = self.mod - self.mod // i * modinv[self.mod % i] % self.mod
        return modinv

    def cmb(self, n, r):
        if n - r < r:
            r = n - r
        if r == 0:
            return 1
        if r == 1:
            return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2, r + 1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p - 1, r, p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result


from sys import stdin
from collections import defaultdict
input = stdin.readline
# ~ T = int(input())
T = 1
for t in range(1,T + 1):