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
Exec Time 32 ms
Memory 9304 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample00, sample01, sample02
All 400 / 400 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 18 ms 9084 KB
case04 24 ms 9080 KB
case05 21 ms 8912 KB
case06 24 ms 9084 KB
case07 20 ms 8944 KB
case08 23 ms 9088 KB
case09 26 ms 9160 KB
case10 22 ms 8932 KB
case11 30 ms 9156 KB
case12 22 ms 8964 KB
case13 32 ms 9304 KB
case14 24 ms 8980 KB
case15 22 ms 9220 KB
case16 24 ms 9024 KB
case17 25 ms 9236 KB
case18 27 ms 9168 KB
case19 24 ms 9076 KB
sample00 31 ms 8936 KB
sample01 20 ms 8920 KB
sample02 30 ms 9132 KB