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

Собирать машинки и домики Васе было не интересно, поэтому он сразу же стал собирать детальки обратно в коробку. Однако ему так понравилось это занятие, что он решил каждый день рассыпать свой конструктор на пол и собирать обратно. Через некоторое время он заметил, что каждый раз детальки складываются в коробку по-разному. Ему стало интересно, сколько существует различных способов, которыми он может уложить свой конструктор обратно в коробку.

Входные данные

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

Выходные данные

Выведите количество способов сложить конструктор. Ответ вывести по модулю 109 + 7.