B. Коля ба Таня

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Коля дугуй ширээнд үлгэрт гардаг жижиг одой хүмүүсийг байрлуулж зоос өгөх дуртай ба Таня зөв гурвалжны оройнууд дээр сууж буй гурвалсан одой хүмүүсийг судлах дуртай.

Албан ёсоор бол $3n$ одой хүмүүс дугуй ширээн дээр сууж байна. Одой хүн бүр $1$-c $3$ зоостой байж болно. Дугуй ширээн дээр $0$-с $3n - 1$ дугаараар тааралдах дарааллаар байрлалуудыг дугаарлацгаая, $i$-р байрлал дээрх одой хүн $a_{i}$ зоостой байхыг зөвшөөрье. Хэрвээ $a_{i} + a_{i + n} + a_{i + 2n} ≠ 6$ шиг байх $i$ ($0 ≤ i < n$) бүхэл тоо байвал Таня сэтгэл хангалуун байна.

Таня сэтгэл хангалуун байх $a_{i}$-г сонгох замуудын тоог ол. Зоосуудыг тараах олон зам байж болох учир уг тооны $10^{9} + 7$ тоонд хуваагаад гарсан үлдэгдлийг хэвлэнэ үү. Хэрвээ $a_{i} ≠ b_{i}$ (уг хоёр арга замд ижил одой хүн өөр зоостой байвал) шиг $i$ ($0 ≤ i < 3n$) индекс байвал $a$ ба $b$ зам нь ялгаатай гэж тооцогдоно.

Оролт

Гуравт хуваагдах одой хүмүүсийн тоо $n$ ($1 ≤ n ≤ 10^{5}$)-г агуулсан ганц мөр байна.

Гаралт

Таняг сэтгэл хангалуун байлгах зоосны тараалтын боломжуудын тоог $10^{9} + 7$ тоонд хуваагаад гарах үлдэгдлийг илэрхийлэх нэг ширхэг бүхэл тоон утгыг хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
1
Гаралт
20
Оролт
2
Гаралт
680

Тэмдэглэл

$n = 1$ үед $20$ боломж байна ($0$ индекстэй одой хүн гурвалжингийн дээд оройд сууна, $1$ дугаартай одой хүн баруун оройд, $2$ дугаартай одой хүн зүүн оройд):

Сэтгэгдлүүдийг ачааллаж байна...