You are given K indices, A[1], A[2], ... , A[K].

A[1] < A[2] < ... < A[K].

A[1] = 1 and A[K] = N.

A permutation of the numbers between 1 and N is called valid if :

The numbers in the permutation between indices A[1] and A2 form an increasing sequence, the numbers in the permutation between indices A[2] and A3 form a decreasing sequence, those between A[3] and A4 form an increasing sequence and so on.

Count the number of valid permutations.

Constraints: 2 <= N <= 20000 2 <= K <= 22 K <= N A[1] < A[2] < ... < A[K]. A[1] = 1 and A[K] = N.

Example: 1. A[]={1,2,3} K=3 answer:2 {(1,3,2),(2,3,1)} 2. A[]={1,3,4} K=3 answer:3 {(1,2,4,3),(1,3,4,2),(2,3,4,1)} Only need count of such permutations . I am unable to get any recursion and things are getting more complicated.My observation is that there are only max 22 K ,but unable to figure out the solution.Problem