Коля любит рассаживать гномов по кругу и раздавать им монеты, а Таня любит изучать тройки гномов, сидящих в вершинах равностороннего треугольника.

Более формально, в круге сидят 3n гномов. У каждого гнома может быть от 1 до 3 монет. Пронумеруем места в порядке следования по кругу числами от 0 до 3n - 1, пусть у гнома, сидящего на i месте, a_i монет. Тогда если существует целое число i (0 ≤ i < n) такое, что a_i + a_i + n + a_i + 2n ≠ 6, то Таня остается довольна.

Посчитайте количество способов выбрать a_i так, чтобы Таня осталась довольна. Так как способов раздачи монет может быть много, вычислите остаток от их деления на 10⁹ + 7. Два способа a и b считаются различными, если существует индекс i (0 ≤ i < 3n) такой, что a_i ≠ b_i (то есть, какой-то гном получил разное количество монет в этих двух способах).