497. Drunken Tower of Hanoi
https://projecteuler.net/problem=497
Bob对于有名的数学游戏“河内塔”非常熟练。该游戏由三个直立圆柱以及若干中间穿洞
且大小各异的圆盘组成，其中圆盘的洞都至少大到能穿进圆柱。一开始，所有n个圆盘都
穿在最左边的圆柱上且由大至小往上堆叠。游戏的目标是要将这些圆盘全数运到最右边的
柱子上，但移动过程有下列几个条件要遵守：
　1. 一次只能移动一个圆盘。
　2. 一次移动是指把一个柱子最上面的圆盘移到另一个柱子上。
　3. 比较大的圆盘不能堆放在比较小的圆盘上。
现在考虑这个游戏的一个变形：现有一个长条状的房间排著k个瓷砖，并由左而右编号为
1到k。三个圆柱安置在编号a、b、c的瓷砖上。圆盘则一开始都放在编号a瓷砖的圆柱上。
Bob一开始站在b的位置上，并打算用河内塔的规则把圆盘都移到编号c的圆柱上。然而，
他只能在和柱子位于同一个位置时才可以捡起或放下圆盘。
不幸地，Bob喝醉了。在一次移动中，Bob会以相等的机率往左或往右移动一格，除非他
已经在端点上了，此时他就只会折返。然而，即使他移动不受控制，他移动圆盘仍然可以
遵照游戏规则进行，也能正确判断什么时候该捡起或放下圆盘。
下面的动画显示了当n = 3、k = 7、a = 2、b = 4以及c = 6时的一种可能的情况。
https://projecteuler.net/project/images/p497_hanoi.gif
令E(n,k,a,b,c)表示Bob在最佳策略下，完成一次游戏时走的格数的期望值。这里的最佳策
略指的是圆盘捡起的次数为最少。
有趣的是，这个期望值一定是个整数。例如，E(2,5,1,3,5) = 60以及
E(3,20,4,9,17) = 2358。
请求出ΣE(n, 10^n, 3^n, 6^n, 9^n)对1≦n≦10000的和的末九位数。