Buggy algorithm

All submissions for this problem are available.
Lukas was asked to be solve the following problem: 'given a permutation of numbers 1,..,n, calculate the number of inversions in it, i.e., the number of pairs of numbers i, j from 1..n, such that i<j and i comes after j in the permutation'. After thinking about the problem for some time, he has invented the following algorithm: 'for each number in the permutation, if it is located to the right of its correct position in sorted sequence, add to the output value the distance between this two positions'. Formally, Lukas's answer is given as: Sum ( max {0, ipi[i]} ), where pi[i] i s the ithe element of the permutation .
So, for permutation 4,1,2,3, the algorithm would give the answer 0+1+1+1 = 3, and for the permutation 3,4,5,1,2, the answer 0+0+0+3+3 =6.
Obviously, this algorithm is wrong (it gives wrong results e.g. for permutation 3,2,1), but... sometimes it gives correct results.
Lucas would like to calculate what are the chances that this algorithm gives the correct result. Specifically, he wants to know how many different permutations of fixed length, which start with a given prefix (several starting numbers), lead to a correct answer to this problem.
Input
First, an integer t<100, representing the number of test cases. Each test case consists of two integers n and m, where n, 1≤n≤30, is the length of permutation, and m, 0≤m≤n, is the length of the given prefix; then, m distinct integers between 1 and n follow, describing the prefix of the permutation.
Output
For each testcase, output in how many ways we can augment the prefix to a complete permutation so that the algorithm gives correct results.
Example
Input: 3
3 0
5 2 1 4
5 1 3
Output:
5
3
9
Author:  admin 
Tags  admin 
Date Added:  5062009 
Time Limit:  0.540541  1.08108 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, SQL, kotlin, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 