Лего#5110
На Новий Рік Васі подарували дитячий конструктор "Лего". Конструктор складається з однакових деталей, кожна з яких має форму прямокутного паралелепіпеда розмірами 1 \times 1 \times 2. Деталі лежали у прямокутній коробці розміром 1 \times 3 \times 2n, причому вільного місця у коробці не було (тобто деталі займали весь простір).
Збирати машинки та будиночки Васі було не цікаво, тому він одразу ж став збирати деталі назад у коробку. Проте йому так сподобалось це заняття, що він вирішив кожен день розсипати свій конструктор на підлогу і збирати назад. Через деякий час він помітив, що кожного разу деталі складаються у коробку по-різному. Йому стало цікаво, скільки існує різних способів, якими він може скласти свій конструктор назад у коробку.
\InputFileОдне натуральне число (1 \le n \le 100).
\OutputFileВиведіть кількість способів скласти конструктор. Відповідь вивести за модулем 10^9 + 7.
Приклад 1