Cerința

Vecinul meu, Dorel, tocmai s-a mutat la casă şi vrea să-şi vopsească gardul. Fiind îndrăgostit de frumos, a cumpărat 7 cutii de vopsea: roşu, orange, galben, verde, albastru, indigo şi violet. Acum însă, are o dilemă: în câte moduri poate vopsi cele n uluci ale gardului, ştiind că fiecare ulucă poate fi vopsită cu oricare dintre culorile cumpărate?

Date de intrare

Fișierul de intrare rogvaiv.in conține pe prima linie numărul n.

Date de ieșire

Fișierul de ieșire rogvaiv.out va conține pe prima linie numărul de moduri în care Dorel poate vopsi gardul, modulo 1.000.000.007.

Restricții și precizări

• numărul n are cel mult 1.000.000 de cifre.

Exemplu:

rogvaiv.in

3

rogvaiv.out

343

Explicație

Fiecare ulucă poate fi vopsită cu una din cele 7 culori, deci avem 7•7•7=343 moduri.