태환이는 험준한 정올 산에 사는 마법사이다.

태환이는 험한 산을 이겨내고 자신을 찾아 온 사람들에게 소원을 들어준다.

그런데 지금이 21세기인지라 케이블 카도 설치되고, 산길도 잘 닦여버려서, 이제는 아무나 태환이가 사는 오두막집을 방문할 수 있다.

어쩔 수 없이 태환이는, 자신의 집을 찾아온 손님들 중, 마법의 순열의 가짓수를 알아내는 사람의 소원만 들어주기로 했다.

수열 {1, 2, 3, 4…, N}이 있다.
수열의 원소들을 재배치해서 순열[p₁,p₂,..p_n]을 만들 수 있다.

예를 들면 N = 4일 때,
{1, 2, 3, 4}를 가지고 p=[4,1,3,2] 또는 p=[3,2,4,1]등을
만들 수 있는 것이다.

이 순열에 대해 다음 두 가지 조건이 성립하면 마법의 순열이라고 한다.

#1. 수열 a₁, a₂, a₃, …., a_K가 주어졌을 때, a의 원소에 위치해 있는 순열 p의 구성원은 이웃한 원소들보다 작다.

즉 아래 수식이 성립한다.

Pa_i-1 > Pa_i < Pa_i+1

#2. b₁, b₂, b₃ … b_L 가 주어졌을 때, b의 원소에 위치해 있는 순열 p의 구성원은 이웃한 원소들보다 크다.

즉 아래 수식이 성립한다.

Pb_i-1 < Pb_i > Pb_i+1

이러한 조건을 만족하는 마법의 순열p가 몇 개 있는지만 대답하면, 태환이가 여러분들의 소원을 들어 줄 수 있다.

즉, 여러분이 짝사랑하는 그(그녀)와 이루어지게 할 수도 있고, 이벤트에 당첨되어 제주도 호화여행을 갈 수도 있으며, 여러분들의 올해 KOI점수를 400점 만점으로 만들어줄 수도...있는 학원에 등록할 수 있는 기회를 줄 수도 있다.

수열 [a₁,a₂,...,a_K]과 [b₁,b₂,...,b_L]가 주어졌을 때, 만들 수 있는 마법의 순열의 가짓수를 구하는 프로그램을 작성하라.

마법의 순열 timer 1s memory 256MB

마법의 순열 1s 256MB