別解

1行進むごとに

ので,この変化をプログラムしてやればいい.