fractal любит геометрию, по этому поместим его в привычное ему пространство, двумерную плоскость. Изначально, fractal находится в координате O(0, 0) и смотрит в сторону оси Ox. Ему дали задание, листок и четное число $$$n$$$ $$$(4 \le n \le 10^6)$$$, зачем и почему мало кто знает, но такова судьба. Ему необходимо выполнить ровно n операций, каждая операция происходит следующим образом:

• fractal выбирает любое положительное целое число X.
• Постепенно пройти на X клеток напрямую вперед в сторону, в которую он сейчас смотрит.
• Повернуть либо направо, либо налево и записать выбранный поворот на листок.

Если после выполнения всех операций, fractal оказался в координате O(0, 0) и смотрит в сторону оси Ox, а так же никогда, кроме самого последнего момента последней операции, не был в координате, которую он посещал раньше, то полученная запись на листке будет называться как «ответ» на задание.

Но так как fractal любит все считать и числа Каталана, он захотел посчитать, сколько «ответов» он сможет получить. Так как ответ может быть очень большим, выведите его по модулю $$$10^9 + 7$$$.