Роспись шаров
На столе расположены 2N белых шаров, выложенных в два ряда, образуя прямоугольник размером 2-на-N. У Джона есть большое ведро с черной краской. (Не спрашивайте, зачем.) Он хочет покрасить все шары в черный цвет, но при этом хочет немного развлечься математикой. (Снова, не спрашивайте, зачем.) Сначала он подсчитал количество различных способов покрасить все шары в черный цвет. Вскоре он понял, что ответ — это (2N)! и решил, что это слишком просто. Поэтому он ввел несколько правил, чтобы сделать задачу более интересной.
Первый шар, который Джон красит, может быть любым из 2N шаров.
Каждый следующий шар, который он красит, должен быть смежным с каким-либо уже покрашенным черным шаром. Два шара считаются смежными, если они находятся рядом друг с другом по горизонтали, вертикали или диагонали.
Джон был вполне доволен этими правилами, поэтому он начал подсчитывать количество способов покрасить все шары в соответствии с ними. Сможете ли вы написать программу, которая найдет ответ быстрее, чем Джон?
Входные данные
Входные данные состоят из нескольких тестов. Каждый тест представлен одной строкой, содержащей целое число N, где 1 ≤ N ≤ 1000. Ввод завершается строкой с N = 0.
Выходные данные
Для каждого теста выведите одну строку, содержащую количество возможных способов, которыми Джон может покрасить все 2N шаров в соответствии с его правилами. Число может быть очень большим, поэтому выведите его по модулю 1000000007.