A Standard Walk on the Coordinate Space

Let's consider $A=(a_1, a_2,...,a_6)$ the vector representing the random walk. Each step can be done going up, down, left, right, forwards or backwards. So $a_i \in \{\text{up}, \text{down}, \text{left}, \text{right}, \text{forw}, \text{back}\}$ , $i \in \{1,6\}$ . Let's indicate, for each $a_i$ step, its opposite movement $-a_i$ . For example if $a_i=\text{down}$ , than $-a_i=\text{up}$ and viceversa.

It's clear that for a generic walk $A$ is it possible to come back at the origin at the 6th step only if, for each $a_i$ , there is a $-a_1$ in $A$ . So, over all the $6^6$ possible walk, the ones we are interested in have an opposite movement for each movement. Here's a simple MATLAB code to count the $k$ occurrences

clear
a=combinator(6,6,'p','r');
v={'up' 'down' 'left' 'right' 'back' 'fow'};
k=1;
     for i=1:46656
       for j=1:6
          b(i,j)=v(a(i,j));
       end
      if sum(count(b(i,:),'up'))==sum(count(b(i,:),'down')) && sum(count(b(i,:),'left'))==sum(count(b(i,:),'right')) 
         && sum(count(b(i,:),'back'))==sum(count(b(i,:),'fow'))
         k=k+1;
      end
    end

where $k-1=1860$ . Eventually

$\displaystyle \frac{1860}{6^6}=\frac{1860}{46656}=\frac{155}{3888}=\frac{p}{q}$ .

So $\displaystyle p=\boxed{155}$ .