BOI 2007 Connecting Points Help

Hi, I am currently working on the problem Connecting Points from Matrix Exponentiation and I was unfortunately stuck. I attempted to find editorials for the problem and I only found the official editorial ( However, I was unable to understand the “states” section (especially the DP-like transition) from the bottom of page 23 to page 25. Could anyone explain this section a bit clearly for me ? Looking at AC code didn’t really help as they often simply presented a matrix and did fast exponentiation on it. There were no comments in the code I found that stressed how the matrix was derived (which I found to be the most difficult part of the problem).