Боб очень хорошо знаком с известной математической игрой/головоломкой "ханойская башня". Она состоит из трех вертикальных штырей и дисков разных размеров, которые можно надевать на штыри. Игра начинается со стопки из n дисков, размещенной на самом левом штыре в порядке уменьшения размера диска снизу вверх. Цель игры - переместить все диски с левого штыря на правый при следующих ограничениях:

1. Только один диск может быть перемещен за ход.
2. Ход состоит в снятии самого верхнего диска со штыря и помещении его на верх другой стопки дисков или на пустой штырь.
3. Нельзя помещать диск на диск меньшего размера.

В "пьяном" варианте этой игры рассмотрим длинную комнату длиной в k единиц (квадратных плиток). Каждый квадрат пронумерован от 1 до k в возрастающем порядке. В квадратах с номерами a, b и c расположены три штыря. На штыре в квадрате a находится стопка из n дисков.

Боб начинает игру стоя в квадрате b. Его цель - решить ханойскую башню переместив все диски на штырь в квадрате c. Однако, Боб может взять диск со штыря или положить его на штырь только когда он находится в одном квадрате с этим штырем.

К несчастью, Боб еще и пьян. В каждый свой ход Боб с одинаковой вероятностью может перейти направо или налево в соседний квадрат, кроме случаев, когда Боб находится в одном из концов комнаты. Тогда он может двигаться только в одном направлении. Несмотря на то, что Боб в подпитии, он по-прежнему способен следовать правилам игры и выбирать, когда взять или положить диск на штырь.

Следующая анимация показывает вид сбоку на пример такой игры для n = 3, k = 7, a = 2, b = 4 и c = 6:

Пусть E(n,k,a,b,c) будет ожидаемым количеством квадратов, которые Боб пройдет в течение одной оптимально сыгранной игры. Игра считается сыгранной оптимально при минимальном возможном количестве взятий дисков.

Любопытно, что результат всегда будет целым числом. Например, E(2,5,1,3,5) = 60 и E(3,20,4,9,17) = 2358.

Найдите последние девять цифр числа ∑_{1≤n≤10000} E(n,10ⁿ,3ⁿ,6ⁿ,9ⁿ).