Anna와 행운의 티켓

Anna는 매우 성실한 학생이다. 그래서 대학교의 모든 수업에 참석한다. 매일 아침 그녀는 버스에 타서 E-card를 특수 장치에 대고 $n$자리 십진수(앞에 0이 올 수 있다)가 적힌 티켓을 받는다.

가는 길에 심심함을 달래기 위해 Anna는 티켓이 행운의 티켓인지 확인한다. 그녀는 두 가지 검사 방법을 알고 있다. 첫 번째 방법에 따르면, 짝수 번째 자리에 있는 숫자들의 합이 홀수 번째 자리에 있는 숫자들의 합과 같으면 티켓은 행운의 티켓이다(자리는 왼쪽에서 오른쪽으로 1부터 번호를 매긴다). 두 번째 방법에 따르면, 처음 $\left\lfloor n / 2 \right\rfloor$개 숫자의 합이 마지막 $\left\lfloor n / 2 \right\rfloor$개 숫자의 합과 같으면 행운의 티켓이다(특히 티켓 번호의 길이가 홀수이면 가운데 숫자는 고려하지 않는다).

티켓이 두 방법 모두에 따라 행운의 티켓이면, Anna는 모든 것이 너무 잘 풀린다고 겁을 먹고 그런 티켓을 불운의 티켓이라고 부른다. 물론 어느 방법으로도 행운의 티켓이 아니면 그것도 불운의 티켓이라고 부른다.

Anna는 번호가 회문인(즉, 왼쪽에서 오른쪽으로 읽으나 오른쪽에서 왼쪽으로 읽으나 같은 수인) 불운의 티켓을 보면 매우 화가 난다. 그런 티켓의 개수를 계산하자! 아, 그리고 그런 티켓이 매우 많을 수 있으니 이 수를 $10^9 + 7$로 나눈 나머지를 출력하자.

입력은 한 줄이며, 티켓 번호의 길이 $n$이 주어진다($2 \le n \le 10^6$).

번호가 회문인 $n$자리 불운의 티켓의 개수를 $10^9 + 7$로 나눈 나머지를 출력한다.