Submission #10,882

2024-04-17 18:12:58

python3

Accepted 80/80

17ms

13528 KiB

from sys import stdin
input=stdin.readline

mod=20210108

d={0:1,1:3,2:10,3:33,4:109,5:360}

def f(n):
    if n in d:
        return d[n]
    if n%2==0:
        cur=(f(n//2)**2+f(n//2-1)**2)%mod
        d[n]=cur
        return cur
    # n%2==1
    cur=(f(n//2)*(f(n//2-1)+f(n//2+1)))%mod
    d[n]=cur
    return cur

N=int(input())
print(f(N))

	Sum	Test	Verdict		Time	Memory
base	80/80
		1	Accepted	0/0	17ms	11064 KiB
		2	Accepted	0/0	17ms	11484 KiB
		3	Accepted	4/4	17ms	11612 KiB
		4	Accepted	4/4	17ms	12028 KiB
		5	Accepted	5/5	17ms	12332 KiB
		6	Accepted	5/5	17ms	12652 KiB
		7	Accepted	6/6	17ms	12424 KiB
		8	Accepted	6/6	17ms	12808 KiB
		9	Accepted	7/7	17ms	12744 KiB
		10	Accepted	7/7	17ms	12916 KiB
		11	Accepted	8/8	17ms	13156 KiB
		12	Accepted	8/8	17ms	13412 KiB
		13	Accepted	8/8	17ms	13216 KiB
		14	Accepted	8/8	17ms	13480 KiB
		15	Accepted	2/2	17ms	13528 KiB
		16	Accepted	2/2	17ms	13488 KiB