Submission #16733716


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():
    s = int(input())
    mod = 10**9+7
    mod_c = mod_comb3()
    ans = 0
    for k in range(1,s//3+1):
        ans = (ans + mod_c.comb(s-2*k-1,k-1))%mod
    print(ans)


if __name__=='__main__':
    main()

Submission Info

Submission Time
Task D - Redistribution
User charter
Language Python (3.8.2)
Score 400
Code Size 979 Byte
Status AC
Exec Time 32 ms
Memory 9304 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 20
Set Name Test Cases
Sample sample00, sample01, sample02
All case03, case04, case05, case06, case07, case08, case09, case10, case11, case12, case13, case14, case15, case16, case17, case18, case19, sample00, sample01, sample02
Case Name Status Exec Time Memory
case03 AC 18 ms 9084 KB
case04 AC 24 ms 9080 KB
case05 AC 21 ms 8912 KB
case06 AC 24 ms 9084 KB
case07 AC 20 ms 8944 KB
case08 AC 23 ms 9088 KB
case09 AC 26 ms 9160 KB
case10 AC 22 ms 8932 KB
case11 AC 30 ms 9156 KB
case12 AC 22 ms 8964 KB
case13 AC 32 ms 9304 KB
case14 AC 24 ms 8980 KB
case15 AC 22 ms 9220 KB
case16 AC 24 ms 9024 KB
case17 AC 25 ms 9236 KB
case18 AC 27 ms 9168 KB
case19 AC 24 ms 9076 KB
sample00 AC 31 ms 8936 KB
sample01 AC 20 ms 8920 KB
sample02 AC 30 ms 9132 KB