N23_6544

dp1 = [0] * (10**4 + 10)
dp2 = [0] * (10**4 + 10)
dp1[1] = 1
dp2[1] = 1
#dp1,dp2
#20min
for i in range(2,10**4+10):
    s1 = 0
    s2 = 0
    if i - 3 >= 1:
        s1 += dp1[i - 3]
        s2 += dp2[i - 3]
    if i - 5 >= 1:
        s1 += dp1[i - 5]
        s2 += dp2[i - 5]
    if i % 2 == 0:
        s1 += dp1[i // 2]
        s2 += dp2[i // 2]
    if i == 5000:
        s1 = 0
    if i == 3000:
        s2 = 0
    dp1[i] = s1
    dp2[i] = s2
ans = dp1[10**4] + dp2[10**4]
#print(ans)
s = str(ans)
print(s[-6:])