Submission #13110387


Source Code Expand

Copy
import sys
def input(): return sys.stdin.readline().rstrip()
class mod_comb3:
    def __init__(self,mod=10**9+7,n_max=1):
        self.mod,self.n_max=mod,n_max
        self.fact,self.inv,self.factinv=[1,1],[0,1],[1,1]
        if 1<n_max:setup_table(n_max)
    def comb(self,n,r):
        if r<0 or n<r:return 0
        if self.n_max<n:self.setup_table(n)
        return self.fact[n]*(self.factinv[r]*self.factinv[n-r]%self.mod)%self.mod
    def setup_table(self,t):
        for i in range(self.n_max+1,t+1):
            self.fact.append(self.fact[-1]*i%self.mod)
            self.inv.append(-self.inv[self.mod%i]*(self.mod//i)%self.mod)
            self.factinv.append(self.factinv[-1]*self.inv[-1]%self.mod)
        self.n_max=t

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    f=mod_comb3(mod)
    ans=0
    t=m*pow(m-1,n-1-k,mod)
    for kx in range(k,-1,-1):
        ans+=f.comb(n-1,kx)*t%mod
        t=t*(m-1)%mod
    print(ans%mod)

if __name__=='__main__':
    main()

Submission Info

Submission Time
Task E - Colorful Blocks
User charter
Language Python (3.8.2)
Score 500
Code Size 1025 Byte
Status AC
Exec Time 384 ms
Memory 32840 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 43
Set Name Test Cases
Sample 00-Sample-00, 00-Sample-01, 00-Sample-02
All 00-Sample-00, 00-Sample-01, 00-Sample-02, 01-Handmade-00, 01-Handmade-01, 01-Handmade-02, 01-Handmade-03, 01-Handmade-04, 01-Handmade-05, 01-Handmade-06, 01-Handmade-07, 01-Handmade-08, 01-Handmade-09, 02-Random-00, 02-Random-01, 02-Random-02, 02-Random-03, 02-Random-04, 02-Random-05, 02-Random-06, 02-Random-07, 02-Random-08, 02-Random-09, 02-Random-10, 02-Random-11, 02-Random-12, 02-Random-13, 02-Random-14, 02-Random-15, 02-Random-16, 02-Random-17, 02-Random-18, 02-Random-19, 02-Random-20, 02-Random-21, 02-Random-22, 02-Random-23, 02-Random-24, 02-Random-25, 02-Random-26, 02-Random-27, 02-Random-28, 02-Random-29
Case Name Status Exec Time Memory
00-Sample-00 AC 18 ms 9084 KB
00-Sample-01 AC 20 ms 9280 KB
00-Sample-02 AC 89 ms 16136 KB
01-Handmade-00 AC 18 ms 8976 KB
01-Handmade-01 AC 20 ms 9280 KB
01-Handmade-02 AC 21 ms 9152 KB
01-Handmade-03 AC 20 ms 9216 KB
01-Handmade-04 AC 221 ms 32828 KB
01-Handmade-05 AC 361 ms 32656 KB
01-Handmade-06 AC 223 ms 32756 KB
01-Handmade-07 AC 384 ms 32840 KB
01-Handmade-08 AC 255 ms 30128 KB
01-Handmade-09 AC 102 ms 19388 KB
02-Random-00 AC 21 ms 9264 KB
02-Random-01 AC 23 ms 9224 KB
02-Random-02 AC 21 ms 9184 KB
02-Random-03 AC 21 ms 9236 KB
02-Random-04 AC 19 ms 9176 KB
02-Random-05 AC 21 ms 9104 KB
02-Random-06 AC 18 ms 9172 KB
02-Random-07 AC 21 ms 9216 KB
02-Random-08 AC 20 ms 9124 KB
02-Random-09 AC 18 ms 9296 KB
02-Random-10 AC 19 ms 9292 KB
02-Random-11 AC 20 ms 9100 KB
02-Random-12 AC 22 ms 9104 KB
02-Random-13 AC 18 ms 9164 KB
02-Random-14 AC 20 ms 9016 KB
02-Random-15 AC 19 ms 9180 KB
02-Random-16 AC 57 ms 11936 KB
02-Random-17 AC 147 ms 18196 KB
02-Random-18 AC 165 ms 19516 KB
02-Random-19 AC 299 ms 29652 KB
02-Random-20 AC 174 ms 23064 KB
02-Random-21 AC 47 ms 12628 KB
02-Random-22 AC 310 ms 30124 KB
02-Random-23 AC 309 ms 31764 KB
02-Random-24 AC 128 ms 20796 KB
02-Random-25 AC 240 ms 26168 KB
02-Random-26 AC 34 ms 10412 KB
02-Random-27 AC 315 ms 31272 KB
02-Random-28 AC 152 ms 21156 KB
02-Random-29 AC 105 ms 18860 KB