(This puzzle continues the puzzle "The frog concerto".)
There is another pond that contains $39$ waterlilies that are arranged in a rectangular $3\times13$ grid. One saturday evening $39$ frogs give a croaking concerto for the residents of the pond.
At the beginning of the concert, the $k$th frog is sitting on the $k$th lily pad (where $1\le k\le39$). There is a short break in the middle of the concert, and after this break none of the frogs returns to its old lily pad. It turns out that after the break each of the $39$ lily pads again carries one frog, and that every frog is now sitting on some new pad that is horizontally or vertically adjacent to its old pad from before the break.
Question: How many different seating arrangements are there after the break that match the above description.
(The answer to this question will be a square number. A good solution will clearly explain the reason why a square number shows up here.)