ある出力を生む経路は複数存在する。経路の集合をその出力の等しさで割って同値類を作り、特にその代表元を上手く選びたい。経路の初期状態での赤い積み木の数が最小となるようなものをそのそのような代表元とすると上手くいく。そのような場合、経路中で赤い積み木の数が$0$になるような時刻が存在することが示せる。ここから逆に、単純な経路の数のDPをして、経路中で一度以上赤い積み木の数が$0$になるような経路の総数を数えればこれはちょうど代表元の数を数えることに等しい。これは$O(NM)$のDPなので解けた。