N23_v2

dp1 = [0]* (10**4 + 10)
dp2 = [0] * (10**4 + 10)
dp1[1] = 1
for i in range(2,3000):
    s = 0
    if i - 3 >= 1:
        s += dp1[i - 3]
    if i - 5 >= 1:
        s += dp1[i - 5]
    if i % 2 == 0:
        s += dp1[i // 2]
    dp1[i] = s
dp1[3000] = 1
for i in range(3001,10**4+10):
    if i == 5000:
        continue
    s = 0
    if i - 3 >= 3000:
        s += dp1[i - 3]
    if i - 5 >= 3000:
        s += dp1[i - 5]
    if i % 2 == 0 and i // 2 >= 3000:
        s += dp1[i // 2]
    dp1[i] = s
to3000 = dp1[1500] + dp1[2997] + dp1[2995]
A = to3000 * dp1[10**4]

dp2[1] = 1
for i in range(2,5000):
    if i == 3000:
        continue
    s = 0
    if i - 3 >= 1:
        s += dp2[i - 3]
    if i - 5 >= 1:
        s += dp2[i - 5]
    if i % 2 == 0:
        s += dp2[i // 2]
    dp2[i] = s
dp2[5000] = 1
for i in range(5001, 10**4 + 10):
    s = 0
    if i - 3 >= 5000:
        s += dp2[i - 3]
    if i - 5 >= 5000:
        s += dp2[i - 5]
    if i % 2 == 0 and i // 2 >= 5000:
        s += dp2[i // 2]
    dp2[i] = s
to5000 = dp2[2500] + dp2[4997] + dp2[4995]
B = to5000 * dp2[10**4]
C = A + B
s = str(C)
print(s[-6:])