문제

평소에 다른 사람이 만든 정렬 문제만 풀던 피돌이는 이제 문제 풀이에 질렸다! 그래서 피돌이는 버블 정렬의 과정에서 아이디어를 얻어온 인접 요소 교환을 통해 자신이 정한 개의 소원을 만족하는 길이가 인 순열 를 찾는 문제를 만들기로 했다. 길이가 인 순열이란 부터 까지의 정수가 한 번씩 등장하는 수열을 말한다.

인접 요소 교환이란, 다음 행동을 순차적으로 한 번 수행하는 것을 말한다.

• 과 를 비교하여 가 더 크면 그대로 두고 더 작으면 둘의 위치를 바꾼다.
• 와 을 비교하여 이 더 크면 그대로 두고 더 작으면 둘의 위치를 바꾼다.
• 과 을 비교하여 이 더 크면 그대로 두고 더 작으면 둘의 위치를 바꾼다.

즉, 한 번의 인접 요소 교환에서 번의 비교와 위치 교환 시도가 일어난다. 예를 들어, 에 인접 요소 교환을 한 번 한 경우, 이 된다.

피돌이가 만든 문제의 순열 는 개의 소원을 모두 만족해야 한다. 번째 소원은 두 정수 와 로 나타내며, 이는 에 인접 요소 교환을 한 번 한 후의 값이 인접 요소 교환 전의 값과 같아야 한다는 뜻이다.

피돌이는 로 가능한 순열을 모두 구해보고 싶었지만 너무 많다 생각하여 개수만 구하기로 하였다. 단, 개수가 너무 커질 수 있으므로 개수를 로 나눈 나머지를 구해보자.

입력

첫째 줄에 테스트 케이스의 개수 가 주어진다.

각 테스트 케이스의 첫째 줄에 순열의 길이 이 주어진다.

각 테스트 케이스의 둘째 줄에 소원의 개수 가 주어진다.

각 테스트 케이스의 다음 줄에 정수 가 공백을 두고 주어진다.

주어지는 모든 소원은 다름이 보장된다. 즉 이면 이다.

모든 테스트 케이스에서 의 합은 을 넘지 않는다.

출력

각 테스트 케이스의 첫째 줄에 가능한 순열 의 개수를 로 나눈 나머지를 출력한다.

노트

첫 번째 테스트케이스에서 가능한 순열 로는 , , 가 있다.