Hi!
On recent OpenCup — Makoto Soejima Contest 4, problem "Random Walk" was posed. We were requested to determine the expected number of visited cells after n steps of random walk on a plane — in each move from (i, j) we go either to (i+1, j), (i-1, j), (i, j+1) or (i, j-1) — all with prob 1/4. More precisely, we needed to output , where M was some integer. In this problem constraint was n ≤ 5000. Actually, this problem becomes much more interesting if we try to solve it for n ≤ 10⁵ in a reasonable time (assume M = 10⁹ + 7 for simplicity). Can you see the solution (if I'm not mistaken — it exists)?