容易想到排列组合解决本题

在$n$步中选择前后左右的步数，

不难发现，若想走回原点

$$走左的步数=走右的步数，走前的步数=走后的步数$$

又因我们知道总步数为$n$,我们只需要一个方向的步数$p$就能推出四个方向的步数

相反方向：p

另外两个方向：显然，$\frac {n-2p} 2=\frac{n}{2}-p$

所以我们枚举$p(0<=p<= \frac n 2)$，然后在n步中选择

走第一个方向，在$n$中选$p$步——$C^p_n$

走相反方向，在剩下的$n-p$中选$p$步——$C^p_{n-p}$

走另一个方向，在剩下的$n-2p$中选$\frac{n}{2}-p$步——$C^{\frac{n}{2}-p}_{n-p}$

剩下的步数全分给最后一个方向

所以答案是

$$ans=\sum_{p=0}^{p<=\frac n2 } C^p_n *C^p_{n-p}*C^{\frac{n}{2}-p}_{n-p} $$