На Новий Рік ЛКШаті Васі подарували дитячий конструктор "Лего". Конструктор складається з 3n однакових детальок, кожна з яких має форму прямокутного паралелепіпеда розмірами 1 × 1 × 2. Детальки лежали у прямокутній коробочці розміром 1 × 3 × 2n, причому вільного місця у коробочці не було (тобто детальки займали увесь простір).

Збирати машинки та будиночки Васі було не цікаво, тому він відразу ж став збирати детальки назад у коробку. Проте йому так сподобалось цео заняття, що він вирішив кожен день розсипати свій конструктор на підлогу і збирати назад. Через деякий час він помітив, що кожен раз детальки складуються у коробку по-різному. Цому стало цікаво, скільки існує різних способів, якими він може скласти свій конструктор назад у коробку.

Вхідні дані

Одне натуральне число n (1 ≤ n ≤ 100).

Вихідні дані

Виведіть кількість способів скласти конструктор. Відповідь вивести за модулем 109 + 7.