Задача 2015Tr2. На столі лежить ряд трикутників, побудованих таким чином. Перший – це правильний трикутник з вершиною догори і одиничною стороною. Називатимемо його «нормально стоячим» Другий утворили так: перший поставили «догори дригом» і до кожної сторони притулили по такому ж попередньому «нормально стоячому» трикутнику Третій і всі наступні утворювали таким же способом: «догори дригом» ставили попередній і додавали 3 попередніх догори вершиною (див. малюнок). Скільки «нормально стоячих» (вершиною догори) трикутників різного розміру у трикутнику з номером N?
Технічні умови. Програма 2015Tr2 читає з пристрою стандартного введення число N (1 <= N <= 1000) - номертрикутника, який ми «обраховуємо», Програма виводить на пристрій стандартного виведення шукану кількість різних трикутників, що стоять «нормально» Виведіть відповідь на задачу за модулем 109 + 7.
Приклади
Введення 2
Виведення 4
Введення 3
Виведення 20
==============