eolymp
bolt
Try our new interface for solving problems

Лего

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 122 MiB

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

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

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
1
Çıxış verilənləri #1
3