1904 01타일

00과 1로 길이 N을 채우려 할 때 가능한 경우의 수를 구하는 문제이다.

몇번 계산해보면 피보나치로 증가하는것을 알 수 있다.

따라서 피보나치를 구해주면되는데, 값이 너무 커지기 때문에 나머지연산을 해주어야 한다.
피보나치에 나머지 연산을 적용하려면 두 수를 더해주는 곳에 적용해주면 된다.

소스