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