기차

기차는 서로 다른 객차를 이용해 여러 가지 방식으로 구성할 수 있다. 여기서는 그 방식이 몇 가지인지 알아내는 프로그램을 작성해야 한다. 기차에는 우편차(M), 여객차(P), 식당차(R), 화물차(G)의 네 가지 서로 다른 유형의 객차가 포함될 수 있다. 기관차는 객차로 세지 않으므로 구성에 포함되지 않는다.

구성에는 다음 규칙이 적용된다:

• 우편차는 기차의 맨 앞, 즉 기관차 바로 뒤나 다른 우편차 뒤에만 연결할 수 있다. 우편차는 최대 두 대까지 있을 수 있지만, 한 대도 없어도 된다.

• 식당차는 항상 두 여객차 사이에 있어야 한다. 식당차는 몇 대든 있을 수 있지만, 한 대도 없어도 된다.

• 여객차는 적어도 한 대 있어야 하며, 몇 대든 있을 수 있다.

• 화물차는 항상 기차의 맨 뒤에 연결한다. 화물차 뒤에는 다른 화물차만 올 수 있다. 화물차는 최대 세 대까지 있을 수 있지만, 한 대도 없어도 된다. 프로그램은 기차에 객차가 몇 대 포함되는지 입력받은 다음, 구성할 수 있는 서로 다른 기차의 수를 계산하여 출력해야 한다.

입력은 정수 $1 \le n \le 30$ 하나로 이루어진다. 이는 기차의 객차 수이다.

만들 수 있는 기차의 수를 출력한다.