Problem: We have a grid of squares with N rows and M columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left. We will choose K of the squares and put a piece on each of them.  If we place the K pieces on squares (x_1, y_1), (x_2, y_2), ..., and (x_K, y_K), the _cost_ of this arrangement is computed as:  \sum_{i=1}^{K-1} \sum_{j=i+1}^K (|x_i - x_j| + |y_i - y_j|)  Find the sum of the costs of all possible arrangements of the pieces. Since this value can be tremendous, print it modulo 10^9+7.  We consider two arrangements of the pieces different if and only if there is a square that contains a piece in one of the arrangements but not in the other.

Submission attempts (in order):
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N,M,K=map(int,input().split())
keisuu=cmb(N*M-2,K-2,10**9+7)

A=10**4
mod = 10**9+7
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, A + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

keisuu=cmb(N*M-2,K-2,mod)

sum_=0
for i in range(N):
    a=min(abs(i),abs(N-i-1))
    b=max(abs(i),abs(N-i-1))
    sum_+=(M**2)*((a*(a+1)//2)+(b*(b+1)//2))
for i in range(M):
    a=min(abs(i),abs(M-i-1))
    b=max(abs(i),abs(M-i-1))
    sum_+=(N**2)*((a*(a+1)//2)+(b*(b+1)//2))
print(keisuu * (sum_//2))

def power_mod(a,b,mod=10**9+7):
    i,temp,box=0,b,[]
    while(2**i<=b):
        i+=1
    for j in range(i-1,-1,-1):
        box=[[j,temp//2**j]]+box
        temp-=2**j*(temp//2**j)
    box[0].append(a)
    ans=box[0][1]*a%mod
    for j in range(1,i):
        box[j].append(box[j-1][2]**2%mod)
        if box[j][1]==1:
            ans=(ans*box[j][2])%mod
    return ans
def n_func(n,mod=10**9+7):
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%mod
    return ans
def nPr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)
    ans=power_mod(ans,mod-2,mod)
    return ans*n_func(n,mod)%mod
def nCr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)*n_func(r,mod)%mod
    ans=power_mod(ans,mod-2,mod)
    return ans*n_func(n,mod)%mod

N,M,K=map(int,input().split())
keisuu=nCr(N*M-2,K-2)

sum_=0
for i in range(N):
    a=min(abs(i),abs(N-i-1))
    b=max(abs(i),abs(N-i-1))
    sum_+=(M**2)*((a*(a+1)//2)+(b*(b+1)//2))
for i in range(M):
    a=min(abs(i),abs(M-i-1))
    b=max(abs(i),abs(M-i-1))
    sum_+=(N**2)*((a*(a+1)//2)+(b*(b+1)//2))
print((keisuu * (sum_//2))%mod)

def power_mod(a,b,mod=10**9+7):
    i,temp,box=0,b,[]
    while(2**i<=b):
        i+=1
    for j in range(i-1,-1,-1):
        box=[[j,temp//2**j]]+box
        temp-=2**j*(temp//2**j)
    box[0].append(a)
    ans=box[0][1]*a%mod
    for j in range(1,i):
        box[j].append(box[j-1][2]**2%mod)
        if box[j][1]==1:
            ans=(ans*box[j][2])%mod
    return ans
def n_func(n,mod=10**9+7):
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%mod
    return ans
def nPr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)
    ans=power_mod(ans,mod-2,mod)
    return ans*n_func(n,mod)%mod
def nCr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)*n_func(r,mod)%mod
    ans=power_mod(ans,mod-2,mod)
    return ans*n_func(n,mod)%mod

N,M,K=map(int,input().split())
keisuu=nCr(N*M-2,K-2,mod)

sum_=0
for i in range(N):
    a=min(abs(i),abs(N-i-1))
    b=max(abs(i),abs(N-i-1))
    sum_+=(M**2)*((a*(a+1)//2)+(b*(b+1)//2))
for i in range(M):
    a=min(abs(i),abs(M-i-1))
    b=max(abs(i),abs(M-i-1))
    sum_+=(N**2)*((a*(a+1)//2)+(b*(b+1)//2))
print((keisuu * (sum_//2))%mod)

def power_mod(a,b,mod=10**9+7):
    i,temp,box=0,b,[]
    while(2**i<=b):
        i+=1
    for j in range(i-1,-1,-1):
        box=[[j,temp//2**j]]+box
        temp-=2**j*(temp//2**j)
    box[0].append(a)
    ans=box[0][1]*a%mod
    for j in range(1,i):
        box[j].append(box[j-1][2]**2%mod)
        if box[j][1]==1:
            ans=(ans*box[j][2])%mod
    return ans
def n_func(n,mod=10**9+7):
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%mod
    return ans
def nPr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)
    ans=power_mod(ans,mod-2,mod)
    return ans*n_func(n,mod)%mod
def nCr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)*n_func(r,mod)%mod
    ans=power_mod(ans,mod-2,mod)
    return ans*n_func(n,mod)%mod

N,M,K=map(int,input().split())
keisuu=nCr(N*M-2,K-2)
mod=10**9+7

sum_=0
for i in range(N):
    a=min(abs(i),abs(N-i-1))
    b=max(abs(i),abs(N-i-1))
    sum_+=(M**2)*((a*(a+1)//2)+(b*(b+1)//2))
for i in range(M):
    a=min(abs(i),abs(M-i-1))
    b=max(abs(i),abs(M-i-1))
    sum_+=(N**2)*((a*(a+1)//2)+(b*(b+1)//2))
print((keisuu * (sum_//2))%mod)

Verdicts: Runtime Error

Runtime Error

Runtime Error

Accepted