## ALTPERM - Alternating Permutations

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 A[2] (inclusive) form an increasing sequence, the numbers in the permutation between indices A[2] and A[3] (inclusive) form a decreasing sequence, those between A[3] and A[4] (inclusive) form an increasing sequence and so on.

Count the number of valid permutations.

**Input**

There will be multiple test cases. The first line contains the number of test cases T.

There follow 2*T lines, 2 lines for each test case. The first line for each test case contains the numbers N and K. The second line contains K space seperated numbers, ie. A[1] to A[K].

**Output**

Output T lines, one for each test case. All answers should be output MOD 1000000007.

**Example**

Sample Input :

3 3 3 1 2 3 4 3 1 3 4 10 6 1 2 5 7 8 10Sample Output : 2 3 6166

T <= 111 2 <= N <= 20000 2 <= K <= 22

ConstraintsK <= N

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

Added by: | Varun Jalan |

Date: | 2010-01-10 |

Time limit: | 2.318s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |

Resource: | Own Problem, used for Codechef Snackdown http://www.codechef.com/ |