Fox's Dream

The legend of Fox Village says that a wish comes true when all disks of a Tower of Hanoi with 3 pegs and $N$ disks are gathered on one peg.

Disks move under these rules:

• The radius of the $i$-th disk is $i$. ($1 \le i \le N$)
• At all times, the disks on one peg must be ordered so that smaller radii are on top.
• Only the top disk on each peg can be moved.
• A disk can only be placed on top of a peg.
• Only one disk can be moved at a time.

A baby fox in the village heard this legend and decided to try the Tower of Hanoi. The baby fox gathered all the disks on the $K$-th peg and made a wish.

"Let me become the cutest fox in the world!"

Nothing changed for the baby fox.

Disappointed, the baby fox decided to arrange the disks into a shape it finds beautiful. Now a Tower of Hanoi master, the baby fox can move one disk per second. Find the minimum time, in seconds, that the baby fox needs to arrange the disks into the beautiful shape.

The first line contains $N$ and $K$, separated by a space. ($1 \le N \le 1000000$; $1 \le K \le 3$)

The second line contains $N$ integers separated by spaces. The $i$-th number $a_i$ is the peg on which the $i$-th disk sits in the beautiful shape. ($1 \le a_i \le 3$)

The beautiful shape the baby fox imagined satisfies the rules of the Tower of Hanoi.

Print, on the first line, the minimum time in seconds for the baby fox to build the beautiful shape, modulo $10^{9} + 7$. $10^{9} + 7$ is a prime.

If the beautiful shape cannot be built, print -1.

Is the legend of Fox Village true?