Problem:


Score : 500 points

Problem Statement

Count the pairs of length-N sequences consisting of integers between 1 and M (inclusive), A_1, A_2, \cdots, A_{N} and B_1, B_2, \cdots, B_{N}, that satisfy all of the following conditions:

A_i \neq B_i, for every i such that 1\leq i\leq N.

A_i \neq A_j and B_i \neq B_j, for every (i, j) such that 1\leq i < j\leq N.

Since the count can be enormous, print it modulo (10^9+7).

Constraints

1\leq N \leq M \leq 5\times10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M

Output

Print the count modulo (10^9+7).

Sample Input 1

2 2

Sample Output 1

2

A_1=1,A_2=2,B_1=2,B_2=1 and A_1=2,A_2=1,B_1=1,B_2=2 satisfy the conditions.

Sample Input 2

2 3

Sample Output 2

18

Sample Input 3

141421 356237

Sample Output 3

881613484



Sample input:
2 2


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
#from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
from collections import deque
#import numba

def generate_inv(n,mod):
    """
    逆元行列
    n >= 2
    Note: mod must bwe a prime number
    """
    ret = [0, 1]
    for i in range(2,n+1):
        next = -ret[mod%i] * (mod // i)
        next %= mod
        ret.append(next)
    return ret

def generate_comb_m_i(M, inv, mod):
    ret = [1, M]
    for i in range(2, M+1):
        tmp = ret[-1]
        tmp *= M-(i-1)
        tmp %= mod
        tmp *= inv[i]
        tmp %= mod
        ret.append(tmp)
    return ret
def generate_p_N_i(N, mod):
    ret = [1]
    for i in range(1, N+1):
        tmp = ret[-1] * (N - (i-1))
        tmp %= mod
        ret.append(tmp)
    return ret

def generate_p_mi_ni(M, N, mod):
    ret = deque([1])
    cache = deque([1])
    for i in range(1, N+1):
        tmp = cache[0]
        tmp *= M-N+i
        tmp %= mod
        cache.appendleft(tmp)
        ret.appendleft((tmp ** 2) % mod)
    return ret


def run():
    N, M = map(int, input().split())
    mod = 10 ** 9 + 7

    inv = generate_inv(M, mod)

    comb_m_i = generate_comb_m_i(M, inv, mod)
    #print(comb_m_i[0])
    p_N_i = generate_p_N_i(N, mod)
    #print(p_N_i[0])
    p_mi_ni = generate_p_mi_ni(M, N, mod)
    #print(p_mi_ni[0])

    ret = p_mi_ni[0]

    sub = 0
    for i in range(1, N+1):
        tmp = comb_m_i[i]
        tmp *= p_N_i[i]
        tmp %= mod
        tmp *= p_mi_ni[i]
        tmp %= mod
        tmp *= (i%2) * 2 - 1
        tmp %= mod
        sub += tmp

    ret -= sub
    ret %= mod

    print(ret)

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
#from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
from collections import deque
#import numba

def generate_inv(n,mod):
    """
    逆元行列
    n >= 2
    Note: mod must bwe a prime number
    """
    ret = [0, 1]
    for i in range(2,n+1):
        next = -ret[mod%i] * (mod // i)
        next %= mod
        ret.append(next)
    return ret

def generate_comb_m_i(M, inv, mod):
    ret = [1, M]
    for i in range(2, M+1):
        tmp = ret[-1]
        tmp *= M-(i-1)
        tmp %= mod
        tmp *= inv[i]
        tmp %= mod
        ret.append(tmp)
    return ret
def generate_p_N_i(N, mod):
    ret = [1]
    for i in range(1, N+1):
        tmp = ret[-1] * (N - (i-1))
        tmp %= mod
        ret.append(tmp)
    return ret

def generate_p_mi_ni(M, N, mod):
    ret = deque([1])
    cache = deque([1])
    for i in range(1, N+1):
        tmp = cache[0]
        tmp *= M-N+i
        tmp %= mod
        cache.appendleft(tmp)
        ret.appendleft((tmp ** 2) % mod)
    return ret


def run():
    N, M = map(int, input().split())
    mod = 10 ** 9 + 7

    inv = generate_inv(M, mod)

    comb_m_i = generate_comb_m_i(M, inv, mod)
    #print(comb_m_i[0])
    p_N_i = generate_p_N_i(N, mod)
    #print(p_N_i[0])
    p_mi_ni = generate_p_mi_ni(M, N, mod)
    #print(p_mi_ni[0])

    ret = p_mi_ni[0]

    sub = 0
    for i in range(1, N+1):
        tmp = comb_m_i[i]
        tmp *= p_N_i[i]
        tmp %= mod
        tmp *= p_mi_ni[i]
        tmp %= mod
        tmp *= (i%2) * 2 - 1
        tmp %= mod
        sub += tmp

    ret -= sub
    ret %= mod

    print(ret)




if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
#from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
from collections import deque
#import numba

def generate_inv(n,mod):
    """
    逆元行列
    n >= 2
    Note: mod must bwe a prime number
    """
    ret = [0, 1]
    for i in range(2,n+1):
        next = -ret[mod%i] * (mod // i)
        next %= mod
        ret.append(next)
    return ret

def generate_comb_m_i(M, inv, mod):
    ret = [1, M]
    for i in range(2, M+1):
        tmp = ret[-1]
        tmp *= M-(i-1)
        tmp %= mod
        tmp *= inv[i]
        tmp %= mod
        ret.append(tmp)
    return ret
def generate_p_N_i(N, mod):
    ret = [1]
    for i in range(1, N+1):
        tmp = ret[-1] * (N - (i-1))
        tmp %= mod
        ret.append(tmp)
    return ret

def generate_p_mi_ni(M, N, mod):
    ret = deque([1])
    cache = deque([1])
    for i in range(1, N+1):
        tmp = cache[0]
        tmp *= M-N+i
        tmp %= mod
        cache.appendleft(tmp)
        ret.appendleft(pow(tmp, 2, mod))
    return ret


def run():
    N, M = map(int, input().split())
    mod = 10 ** 9 + 7

    inv = generate_inv(M, mod)

    comb_m_i = generate_comb_m_i(M, inv, mod)
    p_N_i = generate_p_N_i(N, mod)
    p_mi_ni = generate_p_mi_ni(M, N, mod)
    #print(comb_m_i)
    #print(p_N_i)
    #print(p_mi_ni)


    ret = p_mi_ni[0]

    sub = 0
    for i in range(1, N+1):
        tmp = comb_m_i[i]
        tmp *= p_N_i[i]
        tmp %= mod
        tmp *= p_mi_ni[i]
        tmp %= mod
        tmp *= (-1) ** (i-1)
        tmp %= mod
        sub += tmp

    ret -= sub
    ret %= mod

    print(ret)




if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
#from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
from collections import deque
#import numba

def generate_inv(n,mod):
    """
    逆元行列
    n >= 2
    Note: mod must bwe a prime number
    """
    ret = [0, 1]
    for i in range(2,n+1):
        next = -ret[mod%i] * (mod // i)
        next %= mod
        ret.append(next)
    return ret

def generate_comb_m_i(M, inv, mod):
    ret = [1, M]
    for i in range(2, M+1):
        tmp = ret[-1]
        tmp *= M-(i-1)
        tmp %= mod
        tmp *= inv[i]
        tmp %= mod
        ret.append(tmp)
    return ret
def generate_p_N_i(N, mod):
    ret = [1]
    for i in range(1, N+1):
        tmp = ret[-1] * (N - (i-1))
        tmp %= mod
        ret.append(tmp)
    return ret

def generate_p_mi_ni(M, N, inv, mod):
    ret = deque([1])
    for i in range(1, N+1):
        tmp = ret[0]
        tmp *= M-N+i
        tmp %= mod
        ret.appendleft(tmp)
    return ret


def run():
    N, M = map(int, input().split())
    mod = 10 ** 9 + 7

    inv = generate_inv(M, mod)

    comb_m_i = generate_comb_m_i(M, inv, mod)
    p_N_i = generate_p_N_i(N, mod)
    p_mi_ni = generate_p_mi_ni(M, N, inv, mod)
    #print(comb_m_i)
    #print(p_N_i)
    #print(p_mi_ni)


    ret = pow(p_mi_ni[0], 2, mod)

    sub = 0
    for i in range(1, N+1):
        tmp = comb_m_i[i]
        tmp *= p_N_i[i]
        tmp %= mod
        tmp *= pow(p_mi_ni[i], 2, mod)
        tmp %= mod
        tmp *= (-1) ** (i-1)
        tmp %= mod
        sub += tmp

    ret -= sub
    ret %= mod

    print(ret)




if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
def makefac(n):
    global faclist
    faclist = [1, 1]
    for i in range(2, n + 1):
        faclist.append(faclist[-1] * i % MOD)
    return None
def mcomb(n, r):#nCr % MOD
    return faclist[n] * pow(faclist[r],MOD - 2, MOD) * pow(faclist[n-r], MOD - 2, MOD)
def mperm(n, r):#nPr % MOD
    return faclist[n] * pow(faclist[n-r],MOD - 2, MOD)

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
makefac(M)
ans = mperm(M, N)
for k in range(1, N + 1):
    ans += ((-1)**k * mcomb(N, k) * mperm(M - k, N - k)) % MOD
ans = ans * mperm(M, N) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def makefac(n):
    global faclist
    faclist = [1, 1]
    for i in range(2, n + 1):
        faclist.append(faclist[-1] * i % MOD)
    return None
def mcomb(n, r):#nCr % MOD
    return faclist[n] * pow(faclist[r],MOD - 2,MOD) * pow(faclist[n-r], MOD - 2) % MOD
def mperm(n, r):#nPr % MOD
    return faclist[n] * pow(faclist[n-r],MOD - 2, MOD)

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
makefac(M)
ans = mperm(M, N)
for k in range(1, N + 1):
    ans += ((-1)**k * mcomb(N, k) * mperm(M - k, N - k)) % MOD
ans = ans * mperm(M, N) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def main():
    n,m = map(int,input().split())
    MOD = 10**9 + 7

    fact = [1]
    for i in range(m):
        fact.append(fact[-1]*(i+1)%MOD)

    ｍPn = fact[m] * pow(fact[m-n],MOD-2,MOD) % MOD

    a = pow(mPn,2,MOD)
    b = 0
    for i in range(1,n+1):
        nCr = fact[n] * pow(fact[i],MOD-2,MOD) % MOD * pow(fact[n-i],MOD-2,MOD) % MOD
        b += (-1)**(i) * nCr * fact[m-i] % MOD * pow(fact[m-n],MOD-2,MOD) % MOD
        b %= MOD
    ans = a + b * mPn
    print(ans%MOD)


main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    n,m = map(int,input().split())
    MOD = 10**9 + 7

    fact = [1]
    for i in range(m):
        fact.append(fact[-1]*(i+1)%MOD)
    # print(fact)

    ｍPn = fact[m] * pow(fact[m-n],MOD-2,MOD) % MOD

    a = pow(mPn,2,MOD)
    b = 0
    for i in range(1,n+1):
        nCr = fact[n] * pow(fact[i],MOD-2,MOD) * pow(fact[n-i],MOD-2,MOD) % MOD
        b += (-1)**(i) * nCr * fact[m-i] * pow(fact[m-n],MOD-2,MOD) % MOD
        b %= MOD
    ans = a + b * mPn
    print(ans%MOD)


main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
MOD = 10 ** 9 + 7


factorial = [1, 1]
inverse = [1, 1]
invere_base = [0, 1]
for i in range(2, N + M + 1):
    factorial.append((factorial[-1] * i) % MOD)
    invere_base.append((-invere_base[MOD % i] * (MOD // i)) % MOD)
    inverse.append((inverse[-1] * invere_base[-1]) % MOD)


def nCr(n, r):
    if not (0 <= r <= n):
        return 0
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


def nPr(n, r):
    if not (0 <= r <= n):
        return 0
    return nCr(n, r) * factorial[r] % MOD


ans = pow(nCr(M, N) * factorial[N], 2, MOD)
for r in range(1, N + 1):
    p = nCr(M, r) * pow(nCr(M - r, N - r), 2, MOD) * nCr(N, r) * factorial[r] * factorial[N - r] * factorial[N - r] % MOD
    p *= ((-1) ** ((r % 2) ^ 1))
    ans -= p
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=1):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.node_size=len(ls)+1
                self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.node_size=int(input())
        else:
            self.node_size=inp_size
        self.edges,_=GI(self.node_size,self.node_size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.node_size=len(ls)+1
        self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def parent(self,x):
        return self.dfs(0,func=lambda pr,prv,nx,dist:pr,root_v=-1)
 
    def topological_sort(self,x):  # return topological sort of the tree
        tps=[]
        q=deque([x])
        v=[None]*self.node_size
        v[x]=0
        while q:
            c=q.popleft()
            tps.append(c)
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=0
        return tps
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.node_size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.node_size
        self.ETout=[-1]*self.node_size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def doubling_LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.depth=[None]*self.node_size
            self.depth=self.bfs(0,func=lambda pr,prv,nxt,dist:prv+1)
            self.par=self.bfs(0,func=lambda pr,prv,nxt,dist:pr)
            self.db=[self.par]
            for i in range(self.node_size.bit_length()):
                #show(self.db)
                self.db+=[[self.db[-1][self.db[-1][i]] for i in range(self.node_size)]]
            self.LCA_init_stat=True
        dx=self.depth[x]
        dy=self.depth[y]
        if dx>dy:
            dx,dy=dy,dx
        c=self.node_size.bit_length()
        while c>0:
            if dx+c<=dy:
                x=self.db[c][x]
                dx+=1<<c
            c>>=1
        
        if x==y:
            return x
        
        c=self.node_size.bit_length()
        while c>0:
            if self.db[c][x]!=self.db[c][y]:
                x=self.db[c][x]
                y=self.db[c][y]
            c>>=1
        
        return self.par[x]
        
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        #self.st=SegTree(self.node_size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
    def __str__(self):
        return  str(self.edges)
 
    def show(self):
        if all([all([d==1 for nd,d in e]) for e in self.edges]):
            print( [[nd for nd,d in e] for e in self.edges] )
        else:
            print(self)
 
    def dfs2(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        dfs_tr=[]
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
                    dfs_tr+=nb,
        return v,dfs_tr

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    # return boundary index of r such that func({table[i]} =< x , i in [pos,r]
    def right_bound(self,pos,x):
        k=(self.size-pos).bit_length()
        for j in range(k)[::-1]:
            nx=pos+(1<<j)
            if nx<n and self.query(pos,nx+1)<=x:
                pos+=(1<<j)
        return pos
    
    # return boundary index of l such that func({table[i]} =< x , i in [l,pos]
    def left_bound(self,pos,x):
        k=pos.bit_length()
        for j in range(k)[::-1]:
            nx=pos-(1<<j)
            if 0<=nx and self.query(nx,pos+1)<=x:
                pos-=(1<<j)
        return pos
 
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)

show_flg=False
show_flg=True

ans=0

N=10
a=[[0]*N for i in range(N)]

M=5*10**5+10
fac=[1]*(M+1)
ifac=[1]*(M+1)
for i in range(M):
    fac[i+1]=fac[i]*-~i%mo

ifac[M]=pow(fac[M],mo-2,mo)
for i in range(M)[::-1]:
    ifac[i]=ifac[i+1]*-~i%mo

def com(n,m):
    return fac[n]*ifac[n-m]*ifac[m]%mo

def solve(n,m):
    rt=0
    for x in permutations(range(1,m+1)):
        for y in permutations(range(1,m+1)):
            if all([x[i]!=y[i] for i in range(n)]):
                rt+=1
    return rt        

def solve2(n,m):
    rt=fac[m]*ifac[m-n]
    rt*=rt
    for i in range(1,n+1):
        rt+=(-1)**i*com(n,i)*com(m,i)*fac[m-i]*ifac[m-i-(n-i)]*fac[m-i]*ifac[m-i-(n-i)]%mo
    return rt%mo

n,m=LI()
print(solve(n,m))
exit()
T=6
for n in range(1,T):
    for m in range(n,T):
        x=solve(n,m)
        a[n][m]=x

for i in a:
    print(*i)

print(432/24,11520/432)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
M,F=10**9+7,[1]
for i in range(m): F+=[-~i*F[i]%M]
c=lambda n,r: F[n]*pow(F[r]*F[n-r],-1,M)
p=lambda n,r: F[n]*pow(F[n-r],-1,M)
print(sum((-1)**k*c(n,k)*p(m,k)*p(m-k,n-k)**2 for k in range(n+1))%M)

Submission status: Time Limit Exceeded

Solution code:
M=10**9+7
n,m=map(int,input().split())
F=[1]
for i in range(1,m+1): F+=[i*F[-1]%M]
c=lambda n,r: F[n]*pow(F[r]*F[n-r],-1,M)%M
p=lambda n,r: F[n]*pow(F[n-r],-1,M)%M
a=0
for k in range(n+1):
  a+=(-1)**k*c(n,k)*p(m,k)*p(m-k,n-k)**2%M
print(a%M)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
MAXN = 5*(10**5)+5
fact = [1]
ifact = [1]
for i in range(MAXN):
    fact.append(fact[-1] * (i+1) % MOD)
    ifact.append(pow(fact[-1], MOD-2, MOD))
def nCr(n, r):
    return fact[n] * ifact[r] * ifact[n-r] % MOD

def nPr(n, r):
    return fact[n] * ifact[n-r] % MOD

n, m = map(int, input().split())
ans = 0
for k in range(n+1):
    # tmp = pow(nPr(m-k, n-k), 2, MOD) * nPr(m, k) * nCr(n,k) % MOD
    # tmp = nPr(m-k, n-k) * nPr(m, n) * nCr(n,k) % MOD
    tmp = nPr(m-k, n-k) * nCr(n,k) % MOD
    if k%2:
        ans -= tmp
    else:
        ans += tmp
ans = (ans * nPr(m, n) + MOD) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
MAXN = 5*(10**5)+5
f = [1]
ifact = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
    ifact.append(pow(f[-1], MOD-2, MOD))
def nCr(n, r):
    return f[n] * ifact[r] * ifact[n-r] % MOD

def nPr(n, r):
    return f[n] * ifact[n-r] % MOD

n, m = map(int, input().split())
ans = 0
for k in range(n+1):
    # tmp = pow(nPr(m-k, n-k), 2, MOD) * nPr(m, k) * nCr(n,k) % MOD
    tmp = nPr(m-k, n-k) * nPr(m, n) * nCr(n,k) % MOD
    if k%2:
        ans -= tmp
    else:
        ans += tmp
ans = (ans + MOD) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
MAXN = 5*(10**5)+5
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

def nPr(n, r, mod=MOD):
    return f[n] * pow(f[n-r], mod-2, mod) % mod

n, m = map(int, input().split())
ans = 0
for k in range(n+1):
    # tmp = pow(nPr(m-k, n-k), 2, MOD) * nPr(m, k) * nCr(n,k) % MOD
    tmp = nPr(m-k, n-k) * nPr(m, n) * nCr(n,k) % MOD
    if k%2:
        ans -= tmp
    else:
        ans += tmp
ans = (ans + MOD) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
MAXN = 5*(10**5)+5
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

def nPr(n, r, mod=MOD):
    return f[n] * pow(f[n-r], mod-2, mod) % mod

n, m = map(int, input().split())
ans = 0
for k in range(n+1):
    tmp = nPr(m-k, n-k)
    tmp *= tmp
    tmp %= MOD
    tmp *= nPr(m, k)
    tmp %= MOD
    tmp *= nCr(n,k)
    tmp %= MOD
    if k%2:
        ans -= tmp
    else:
        ans += tmp
ans += MOD
ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())

U=10**6
mod=10**9+7

fact=[1]*(U+1)
fact_inv=[1]*(U+1)

for i in range(1,U+1):
    fact[i]=(fact[i-1]*i)%mod
fact_inv[U]=pow(fact[U],mod-2,mod)

for i in range(U,0,-1):
	fact_inv[i-1]=(fact_inv[i]*i)%mod

def comb(n,k):
    if k<0 or k>n:
        return 0
    x=fact[n]
    x*=fact_inv[k]
    x%=mod
    x*=fact_inv[n-k]
    x%=mod
    return x
def div(a,b):
    return (a*pow(b,mod-2,mod))%mod

def p(n,k):
    return div(fact[n],fact[n-k])
ans=0
for i in range(n+1):
    t=(comb(n,i)*p(m-i,n-i))%mod
    if i%2:ans=(ans-t)%mod
    else:ans=(ans+t)%mod
ans=(ans*p(m,n))%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
fact=[1]
for i in range(1,5*10**5+1):
  fact.append((fact[-1]*i)%mod)
revfact=[1]
for i in range(1,5*10**5+1):
  revfact.append(pow(fact[i],mod-2,mod))
n,m=map(int,input().split())
patternA=(fact[m]*revfact[n]*revfact[m-n]*fact[n])%mod
patternB=0
for i in range(n+1):
  tmp=(fact[n]*revfact[i]*revfact[n-i])*(fact[m-i]*revfact[n-i]*revfact[m-n])*fact[n-i]
  if i%2==0:
    patternB+=tmp
    patternB%=mod
  else:
    patternB-=tmp
    patternB%=mod
print((patternA*patternB)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline

def calc():
  mod=10**9+7
  fact=[1]
  for i in range(1,5*10**5+1):
    fact.append((fact[-1]*i)%mod)
  revfact=[1]
  for i in range(1,5*10**5+1):
    revfact.append(pow(fact[i],mod-2,mod))
  n,m=map(int,input().split())
  patternA=(fact[m]*revfact[n]*revfact[m-n]*fact[n])%mod
  patternB=patternA
  for i in range(1,n+1):
    tmp=(fact[n]*revfact[i]*revfact[n-i])*(fact[m-i]*revfact[n-i]*revfact[m-n])*fact[n-i]
    if i%2==0:
      patternB+=tmp
      patternB%=mod
    else:
      patternB-=tmp
      patternB%=mod
  print((patternA*patternB)%mod)
calc()

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
fact=[1]
for i in range(1,5*10**5+1):
  fact.append((fact[-1]*i)%mod)
revfact=[1]
for i in range(1,5*10**5+1):
  revfact.append(pow(fact[i],mod-2,mod))
n,m=map(int,input().split())
patternA=(fact[m]*revfact[n]*revfact[m-n]*fact[n])%mod
patternB=patternA
for i in range(1,n+1):
  tmp=(fact[n]*revfact[i]*revfact[n-i])*(fact[m-i]*revfact[n-i]*revfact[m-n])*fact[n-i]
  if i%2==0:
    patternB+=tmp
    patternB%=mod
  else:
    patternB-=tmp
    patternB%=mod
print((patternA*patternB)%mod)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
mod = 10**9+7
def fact_list(a):
  ans = [1]
  for i in range(1,a+1):
    ans.append(ans[-1]*i % mod)
  return ans

factlist = fact_list(M)

def comb_mod(a,b):
  return (factlist[a]*pow(factlist[b],mod-2,mod)*pow(factlist[a-b],mod-2,mod) )% mod

def permu_mod(a,b):
  return (factlist[a]*pow(factlist[a-b],mod-2,mod) % mod)

ans = 0
for i in range(N+1):
  ans += comb_mod(N,i)*(-1)**i*permu_mod(M,i)*permu_mod(M-i,N-i)**2 
  ans = ans % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def fact_table(N, MOD=10**9 + 7):

    inv = np.empty(N, np.int64)
    fact = np.empty(N, np.int64)
    fact_inv = np.empty(N, np.int64)

    inv[0] = 0
    inv[1] = 1
    for n in range(2, N):
        q, r = divmod(MOD, n)
        inv[n] = inv[r] * (-q) % MOD

    fact[0] = 1
    for n in range(1, N):
        fact[n] = n * fact[n - 1] % MOD

    fact_inv[0] = 1
    for n in range(1, N):
        fact_inv[n] = fact_inv[n - 1] * inv[n] % MOD

    return fact, fact_inv, inv


def main():

    N, M = in_nn()
    mod = 10**9 + 7
    fact, fact_inv, inv = fact_table(M + 1)

    def comb(n, r, mod=10**9 + 7):
        return fact[n] * fact_inv[r] % mod * fact_inv[n - r] % mod

    def perm(n, r, mod=10**9 + 7):
        return fact[n] * fact_inv[n - r] % mod

    ans = 0
    for i in range(N + 1):
        t = comb(N, i)

        t *= (-1)**(i % 2)
        t %= mod

        t *= perm(M, i)
        t %= mod

        t *= perm(M - i, N - i)
        t %= mod

        t *= perm(M - i, N - i)
        t %= mod

        ans += t
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
mod = pow(10, 9)+7
ans = 0
a = 1
b = 1
c = 1
for i in range(m-n+1, m+1):
  b *= i
  b %= mod
for i in range(n+1):
  k = -1 if i%2 else 1
  ans += k*a*b**2*c
  ans %= mod
  a *= m-i
  a %= mod
  b *= pow(m-i, mod-2, mod)
  b %= mod
  c *= n-i
  c *= pow(i+1, mod-2, mod)
  c %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())

#comb
def comb(n, k, p):
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    from math import factorial
    a = factorial(n) % p
    b = factorial(k) % p
    c = factorial(n-k) % p
    return (a * power_func(b, p-2, p) * power_func(c, p-2, p))%p
# perm
def perm(n, k, p):
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    from math import factorial
    a = factorial(n) % p
    c = factorial(n-k) % p
    return (a*power_func(c,p-2,p))%p
def power_func(a, b, p):
    if b==0: return 1
    if b % 2 == 0:
        d = power_func(a,b//2, p)
        return d * d % p
    else:
        return (a * power_func(a, b-1, p))%p
count = 0    
p = 10**9+7
for i in range(n + 1):
    comb1 = comb(n, i, p)
    perm1 = perm(m, i, p)
    perm2 = perm(m-i,n-i, p)
    count += comb1 * (-1)**i*perm1*perm2**2
print(count)