페이션스

사샤는 14열 4행짜리 판에서 페이션스를 한다. 조커를 뺀 52장 카드 한 벌에서 에이스 네 장을 빼내 1열에 놓는다. 칸 (1, 1)에는 다이아몬드 에이스, (1, 2)에는 하트 에이스, (1, 3)에는 클로버 에이스, (1, 4)에는 스페이드 에이스가 놓인다. 칸 $(c, r)$ 은 $c$ 열 $r$ 행을 뜻한다. 남은 카드는 섞은 다음 2열을 건너뛰고 행 순서대로 깔기 때문에, 2열은 빈 채로 남고 3열부터 14열까지가 카드로 덮인다.

카드를 다 깔면 사샤가 카드를 옮긴다. 한 번의 이동은 빈 칸 하나를 고르는 것이다. 그 칸을 덮는 카드는 바로 왼쪽 칸이 정한다. 덮는 카드는 무늬가 같고 숫자가 바로 다음이며, 숫자 순서는 에이스, 2, 3, 4, 5, 6, 7, 8, 9, 10, 잭, 퀸, 킹이다. 예를 들어 칸 (6, 3)에 스페이드 퀸이 있고 칸 (7, 3)이 비어 있으면, (7, 3)을 고를 때 스페이드 킹이 그 자리로 오고 킹이 있던 칸이 빈 칸이 된다. 빈 칸의 왼쪽 칸에 킹이 있거나 그 칸도 비어 있으면 그 빈 칸은 고를 수 없다.

목표는 네 행을 모두 정렬하는 것이다. 1열부터 13열까지 한 무늬의 에이스부터 킹까지가 차례로 놓이고 14열은 비어야 한다. 카드가 아직 정렬되지 않았는데 빈 칸이 모두 킹 뒤나 다른 빈 칸 뒤에 있으면 사샤가 진다. 원래 규칙은 정렬된 카드를 그대로 두고 나머지를 두 번 더 섞게 해 주지만, 사샤는 손에 익어서 다시 섞지 않고도 자주 이긴다.

이제 사샤는 개수를 세고 싶어 한다. 세 무늬는 이미 정렬되었고 남은 한 무늬만 일부까지 정렬된 배치를 생각하자. 그 무늬에서 제자리를 벗어난 높은 카드가 $n$ 장 미만이므로, 오른쪽 $n$ 개 열에만 정렬되지 않은 카드가 놓인다. $n = 3$ 이면 1열부터 11열까지는 정렬되어 있고 12열, 13열, 14열에 퀸과 킹과 빈 칸이 임의의 순서로 놓인다. 이 가운데 지는 배치는 [킹] [빈 칸] [퀸] 하나뿐이다. 빈 칸이 킹 바로 뒤에 있어서 고를 수 없기 때문이다. 나머지 다섯 배치는 모두 이길 수 있다.

[퀸] [킹] [빈 칸]은 이미 목표 배치다.
[퀸] [빈 칸] [킹]은 킹을 퀸 옆으로 옮기면 된다.
[빈 칸] [퀸] [킹]은 퀸을 잭 뒤로 옮기면 2번 배치가 된다.
[빈 칸] [킹] [퀸]은 퀸을 잭 뒤로 옮기면 목표 배치가 된다.
[킹] [퀸] [빈 칸]은 킹을 빈 칸으로 옮기면 3번 배치가 된다.

그래서 $n = 3$ 의 답은 5다. 1 이상 13 이하의 $n$ 이 주어질 때 이길 수 있는 배치의 개수를 세는 프로그램을 작성하라.

문제

입력

출력