How to generate a second order markov chain?

I have 27 symbols (numbers 1 to 27) and a probability transition matrix of size 729*27 for generating a second order markov chain.

I have already done first order one with a 27*27 probability transition matrix. The code snippet for 1st order markov chain was like this:

states = zeros(1,10000);% for 10000 length string output
states(1) = randsample(27, 1, true, prior);% 27 symbols
for t=2:10000
    states(t) = randsample(27, 1, true, TRANS(states(t-1),:));% 27 symbols
end

(where prior is the probability distribution of symbols and TRANS is the transition matrix, states is the generated sequence.) How can I extend this to 2nd order markov chain?