Задача 3015Tr1. На столі лежить ряд трикутників, побудованих таким чином. Перший – це  правильний трикутник з вершиною догори і одиничною стороною. Називатимемо його «нормально стоячим» Другий утворили так: перший поставили «догори дригом» і до кожної сторони притулили по такому ж попередньому «нормально стоячому» трикутнику Третій і всі наступні утворювали таким же способом:  «догори дригом»  ставили попередній і додавали 3 попередніх догори вершиною (див. малюнок). Скільки «нормально стоячих» (вершиною догори) одиничних трикутників у трикутнику з номером N?

Технічні умови. Програма 2015Tr1 читає з пристрою стандартного введення число N (1 <= N <= 1000) - номертрикутника, який ми «обраховуємо», Програма виводить на пристрій стандартного виведення шукану кількість одиничних трикутників, що стоять «нормально» Виведіть відповідь на задачу за модулем 10⁹ + 7.

Приклади

Введення 2

Виведення 3

Введення 3