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