01 타일

길이가 1인 타일에는 숫자 1이 적혀 있고, 길이가 2인 타일에는 숫자 00이 적혀 있다. 두 종류의 타일을 원하는 만큼 사용해서 왼쪽부터 이어 붙이면 하나의 이진 수열을 만들 수 있다.

길이가 N인 이진 수열 중 이런 방식으로 만들 수 있는 수열의 개수를 구하자. 타일은 각 종류마다 충분히 많이 있다고 가정한다.

가령 N = 1이면 만들 수 있는 수열은 1 하나뿐이다. N = 2이면 00, 11을 만들 수 있고, 01과 10은 만들 수 없다. N = 4이면 0011, 0000, 1001, 1100, 1111처럼 총 5개의 수열을 만들 수 있다.

첫 번째 줄에 자연수 N이 주어진다.

1 <= N <= 1,000,000

만들 수 있는 길이 N인 이진 수열의 개수를 15746으로 나눈 나머지를 출력한다.