def foo(n, i, j):
j -= 1
a = [0] * n
a[j] = 1
while i < n:
next = [0] * n
for k in range(n):
if k == 0:
next[k] = a[k + 1]
elif k == n - 1:
next[k] = a[k - 1]
else:
next[k] = a[k - 1] + a[k + 1]
a = next
i += 1
return sum(a)
print(foo(8, 6, 3))
ZGVmIGZvbyhuLCBpLCBqKToKCWogLT0gMQoJYSA9IFswXSAqIG4KCWFbal0gPSAxCgkKCXdoaWxlIGkgPCBuOgoJCW5leHQgPSBbMF0gKiBuCgkJZm9yIGsgaW4gcmFuZ2Uobik6CgkJCWlmIGsgPT0gMDoKCQkJCW5leHRba10gPSBhW2sgKyAxXQoJCQllbGlmIGsgPT0gbiAtIDE6CgkJCQluZXh0W2tdID0gYVtrIC0gMV0KCQkJZWxzZToKCQkJCW5leHRba10gPSBhW2sgLSAxXSArIGFbayArIDFdCgkJCgkJYSA9IG5leHQKCQlpICs9IDEKCQoJcmV0dXJuIHN1bShhKQoJCnByaW50KGZvbyg4LCA2LCAzKSk=