上段 \(i\) 番目, \(i+1\) 番目の数字と下段 \(i+1\) 段目の数字から上段 \(i+1\) 番目, \(i+2\)番目のどの数字に遷移できるかが分かる.

上段 i, i+1 番目 下段 i+1 番目 上段 i+1, i+2 番目
00 0 00
1 01
11 0 11
1 10
01 0 -
1 10,11
10 0 00
1 01

まずは下段1番目の数字から上段の \(N\) 番目, 1番目, 2番目の数字を仮定する.

そして上記の表を使って DP で上段の \(i\) 番目, \(i+1\) 番目の数字ごとに遷移できる組み合わせの数を求める.

端まで計算したら, 最初の仮定と合っている数字の組み合わせ数を取得する.