30190번 - 여우의 꿈

여우 마을에는 $3$개의 기둥과 $N$개의 원판을 가진 하노이 탑의 원판들을 한 곳에 모으면 소원이 이루어진다는 전설이 있다.

하노이 탑의 원판들을 이동시키는 규칙은 다음과 같다.

• $i$번째 원판의 반지름은 $i$이다. ($1\le i\le N$)
• 어떤 시점에라도 한 기둥 안의 원판은 반지름이 작을수록 위로 오도록 정렬되어 있어야 한다.
• 각 기둥의 제일 위에 있는 원판만 이동할 수 있다.
• 원판은 기둥의 맨 위로만 이동할 수 있다.
• 원판은 한 번에 한 개만 이동할 수 있다.

여우 마을에 사는 아기 여우는 어느 날 이 소문을 듣고 하노이 탑에 도전하기로 했다. 아기 여우는 모든 원판을 $K$번째 기둥에 모으는 데 성공했고, 소원을 빌었다.

"세상에서 가장 귀여운 여우가 되게 해주세요!"

하지만 아기 여우에게는 아무런 변화도 일어나지 않았다.

실망한 아기 여우는 이번에는 자신이 생각하기에 아름다운 모양으로 원판을 배치해 보기로 했다. 이제는 하노이 탑의 고수가 된 아기 여우는 $1$초에 한 개의 원판을 옮길 수 있다. 아기 여우가 원판을 아름다운 모양으로 배치하는 데 걸리는 최소 시간을 구해 보자!

첫 번째 줄에 $N$과 $K$가 공백을 사이에 두고 입력된다. ($1\le N \le 1\, 000\, 000$; $1\le K \le3$)

두 번째 줄에 $N$개의 수가 공백을 사이에 두고 입력된다. $i$번째 수 $a_i$는 $i$번째 원판이 아름다운 모양에서 몇 번째 기둥에 있는지 의미한다. ($1\le a_i \le 3$)

아기 여우가 생각한 아름다운 모양은 하노이 탑의 규칙을 만족한다.

첫 번째 줄에 아기 여우가 아름다운 모양을 만드는 데 걸리는 최소 시간(초)을 $10^{9} + 7$로 나눈 나머지를 출력한다. $10^{9} + 7$은 소수이다.

아름다운 모양을 만드는 것이 불가능하면 -1을 출력한다.

여우 마을의 전설은 사실일까요?