「遠回りしない」という条件の下、東西、および、南北の0号、3号で囲まれる
3×3の区画内のいずれかの生活道路を使用する場合、
(1,0)か(2,0)から進入し、(3,1)か、(3,2)から出る場合しかなく、合計5通りある。
つまり、生活道路同士の交差点、(3p+s,3q+t)　(s,t=1,2)を利用する場合、
必ず、大通り同士の交差点(3p,3q)と(3p+3,3q+3)を利用している。

題意の条件に従い、通った大通り同士の交差点のみをプロットし、結ぶと、
“横に変化”、“上に変化”、“斜めに変化”の三通りに分類できる。

“斜めに変化”の回数がk回だとすると、“横に変化”は、n-k回、“上に変化”は3-k回となる。
斜めに変化の場合、生活道路の通り方で、5通りあるので、

Σ[k=0,3] 5^k*((n-k)+(3-k)+k)!/{(n-k)!*(3-k)!*k!}　で計算できることが判る。

答え　36n^3-54n^2+36n+1