Counting King's Hamiltonian Paths through 3-by-N grid
Wolfram Language (Mathematica), 76 72 bytes
LinearRecurrence[{6,12,-27,2,30,4,-6},{0,0,1,2,3,29,155}-6/5,{#+4}]+1/5&amp;

Try it online!
The non-homogeneous linear recurrence equation is so much shorter to express that it saves a few bytes to modify the code to handle non-homogeneous linear recurrence.
More info: In this case, it cannot be represented as a polynomial. I tried to put the recurrence into RSolve, but it takes a long time to figure out the exact symbolic form (I terminate it before it completes), and I'm pretty sure that the required coefficients are irrational (approximate numerical formula can be obtained).
Returns a singleton list containing the result.