405249: GYM101858 A Alluka's Curse

Alluka is possessed by a mysterious creature known as Nanika.

Nanika has a very powerful ability: she can make anything come true once someone asks her.

Of course magic does not exists. Nanika has a secret company that helps her fulfilling the wishes. People very talented work at her command and everything can become possible under talented hands.

You're very talented and work for Nanika, so you have to help her fulfill the wishes as soon as she asks you.

The last wish, as weird as it might sound, is to know how many distinct ways you can fill a $$$3 \times n$$$ grid using only $$$1 \times 2$$$ pieces.

As the answer can be very large, output it modulo $$$10^9+7$$$.

The first line of input contains one integer, $$$n$$$ ($$$1 \le n \le 10^7$$$) — the dimension of the grid.

Print how many distinct ways you can fill the grid.

2

3

3

0

4

11

Image in statement represents test case #1.