Anna 是一位非常勤奋的学生。正因如此，她会参加大学里的每一节课。每天早上，她都会乘坐公交车，刷卡后会得到一张印有 $n$ 位十进制数字的车票（可能包含前导零）。

为了在乘车途中消遣，Anna 会检查车票是否“幸运”。她知道两种验证方法。第一种方法是：如果车票上偶数位置上的数字之和等于奇数位置上的数字之和（位置从左到右编号，从 1 开始），则该车票是幸运的。第二种方法是：如果车票前 $\lfloor n/2 \rfloor$ 位数字之和等于后 $\lfloor n/2 \rfloor$ 位数字之和，则该车票是幸运的（特别地，如果车票长度为奇数，则中间的数字不计入）。

如果一张车票按上述两种方法均被判定为幸运，Anna 会担心一切进行得太顺利，并将这种车票称为“不幸运”的。当然，如果一张车票按上述两种方法均不被判定为幸运，它也被称为“不幸运”的。

当 Anna 看到一张既是“不幸运”的，又是回文数（即从右向左读与从左向右读完全相同）的车票时，她会非常生气。请帮助我们计算这类车票的数量！当然，这类车票可能非常多，请输出其数量对 $10^9 + 7$ 取模的结果。

输入格式

输入包含一个整数 $n$，表示车票数字的长度（$2 \le n \le 10^6$）。

输出格式

输出一个整数：满足条件的 $n$ 位“不幸运”回文车票的数量，结果对 $10^9 + 7$ 取模。

样例

输入 1

3

输出 1

5