여우의 꿈

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

하노이 탑의 원판은 다음 규칙에 따라 옮긴다.

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

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

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

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

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

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

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

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

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

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

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