시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 14 8 8 61.538%

문제

힙찌리 쇼미충 정주경은 음악 듣는 것을 좋아한다. 주경이는 음악을 들을 때 음악 플레이어의 shuffle 기능을 이용한다. 음악 플레이어는 랜덤으로 순열을 생성하여 플레이리스트의 음악을 재생하고, 모든 음악이 다 재생되면 다시 셔플이 되어 음악이 또 재생이 된다.

주경이는 이제껏 재생이 된 음악 목록을 가지고 있었는데, 이 재생 목록이 처음 음악이 재생될 때부터 완벽하게 기록을 하지 않았다는 것을 알게되었다. 이 기록을 가지고 주경이는 다음 셔플이 어떻게 될지를 알고싶어한다.

플레이 리스트의 음악의 수를 s라 할 때 음악 재생 목록을 길이 s인 구간으로 나눌 수 있는데, 처음과 마지막 구간은 s보다 작게끔 나눌수도 있다. 이때 각 구간의 음악은 겹쳐서는 안된다.

입력

첫째 줄에는 테스트케이스의 수가 주어진다. 최대 100이다.

그 이후 각 테스트케이스마다 첫째 줄에는 s와 n(1 ≤ s, n ≤ 100 000)이 주어진다. s는 플레이리스트의 곡의 수이고, n은 이제껏 재생된 곡 목록의 곡의 수이다.

둘째 줄에는 n개의 x1, x2, . . . , xn (1 ≤ xi ≤ s) 재생된 음악이 주어진다.

출력

각 테스트 케이스마다

첫째 줄에 다음 셔플이 어떻게 되는 지 경우의 수를 출력한다. 만약 가능한 경우의 수가 없다면 0을 출력한다.

예제 입력 1

4
4 10
3 4 4 1 3 2 1 2 3 4
6 6
6 5 4 3 2 1
3 5
3 3 1 1 1
7 3
5 7 3

예제 출력 1

1
6
0
7
W3sicHJvYmxlbV9pZCI6IjM2ODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxNTRcdWQ1MGMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDc5OVx1Y2MwY1x1YjlhYyBcdWMxZmNcdWJiZjhcdWNkYTkgXHVjODE1XHVjOGZjXHVhY2JkXHVjNzQwIFx1Yzc0Y1x1YzU0NSBcdWI0ZTNcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzg4Ylx1YzU0NFx1ZDU1Y1x1YjJlNC4gXHVjOGZjXHVhY2JkXHVjNzc0XHViMjk0IFx1Yzc0Y1x1YzU0NVx1Yzc0NCBcdWI0ZTRcdWM3NDQgXHViNTRjIFx1Yzc0Y1x1YzU0NSBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWM3NTgmbmJzcDtzaHVmZmxlIFx1YWUzMFx1YjJhNVx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1Yzc0Y1x1YzU0NSBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWIyOTQgXHViNzljXHViMzY0XHVjNzNjXHViODVjIFx1YzIxY1x1YzVmNFx1Yzc0NCBcdWMwZGRcdWMxMzFcdWQ1NThcdWM1ZWMgXHVkNTBjXHViODA4XHVjNzc0XHViOWFjXHVjMmE0XHVkMmI4XHVjNzU4IFx1Yzc0Y1x1YzU0NVx1Yzc0NCBcdWM3YWNcdWMwZGRcdWQ1NThcdWFjZTAsIFx1YmFhOFx1YjRlMCBcdWM3NGNcdWM1NDVcdWM3NzQgXHViMmU0IFx1YzdhY1x1YzBkZFx1YjQxOFx1YmE3NCBcdWIyZTRcdWMyZGMgXHVjMTU0XHVkNTBjXHVjNzc0IFx1YjQxOFx1YzViNCBcdWM3NGNcdWM1NDVcdWM3NzQmbmJzcDtcdWI2MTAgXHVjN2FjXHVjMGRkXHVjNzc0Jm5ic3A7XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4ZmNcdWFjYmRcdWM3NzRcdWIyOTQgXHVjNzc0XHVjODFjXHVhZWNmIFx1YzdhY1x1YzBkZFx1Yzc3NCBcdWI0MWMgXHVjNzRjXHVjNTQ1IFx1YmFhOVx1Yjg1ZFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjNWM4XHViMjk0XHViMzcwLCBcdWM3NzQgXHVjN2FjXHVjMGRkIFx1YmFhOVx1Yjg1ZFx1Yzc3NCBcdWNjOThcdWM3NGMgXHVjNzRjXHVjNTQ1XHVjNzc0IFx1YzdhY1x1YzBkZFx1YjQyMCZuYnNwO1x1YjU0Y1x1YmQ4MFx1ZDEzMCZuYnNwO1x1YzY0NFx1YmNiZFx1ZDU1OFx1YWM4YyBcdWFlMzBcdWI4NWRcdWM3NDQgXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzU1OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNTRjXHVhYzhjXHViNDE4XHVjNWM4XHViMmU0LiBcdWM3NzQgXHVhZTMwXHViODVkXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCZuYnNwO1x1YzhmY1x1YWNiZFx1Yzc3NFx1YjI5NCBcdWIyZTRcdWM3NGMgXHVjMTU0XHVkNTBjXHVjNzc0IFx1YzViNFx1YjViYlx1YWM4YyBcdWI0MjBcdWM5YzBcdWI5N2MgXHVjNTRjXHVhY2UwXHVjMmY2XHVjNWI0XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1MGNcdWI4MDhcdWM3NzQgXHViOWFjXHVjMmE0XHVkMmI4XHVjNzU4IFx1Yzc0Y1x1YzU0NVx1Yzc1OCBcdWMyMThcdWI5N2Mgc1x1Yjc3YyBcdWQ1NjAmbmJzcDtcdWI1NGMmbmJzcDtcdWM3NGNcdWM1NDUgXHVjN2FjXHVjMGRkIFx1YmFhOVx1Yjg1ZFx1Yzc0NCBcdWFlMzhcdWM3NzQgc1x1Yzc3OCBcdWFkNmNcdWFjMDRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjBjIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1Y2M5OFx1Yzc0Y1x1YWNmYyBcdWI5YzhcdWM5YzBcdWI5YzkgXHVhZDZjXHVhYzA0XHVjNzQwIHNcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzhjXHViMDU0IFx1YjA5OFx1YjIwY1x1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWFjMDEgXHVhZDZjXHVhYzA0XHVjNzU4IFx1Yzc0Y1x1YzU0NVx1Yzc0MCBcdWFjYjlcdWNjZDBcdWMxMWNcdWIyOTQgXHVjNTQ4XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjZDVjXHViMzAwIDEwMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4IFx1Yzc3NFx1ZDZjNCBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgc1x1YzY0MCBuKDEgJmxlOyBzLCBuICZsZTsgMTAwIDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBzXHViMjk0IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YjlhY1x1YzJhNFx1ZDJiOFx1Yzc1OCBcdWFjZTFcdWM3NTgmbmJzcDtcdWMyMThcdWM3NzRcdWFjZTAsIG5cdWM3NDAgXHVjNzc0XHVjODFjXHVhZWNmJm5ic3A7XHVjN2FjXHVjMGRkXHViNDFjJm5ic3A7XHVhY2UxJm5ic3A7XHViYWE5XHViODVkXHVjNzU4IFx1YWNlMVx1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgblx1YWMxY1x1Yzc1OCZuYnNwO3gxLCB4MiwgLiAuIC4gLCB4biZuYnNwOygxICZsZTsgeGkmbmJzcDsmbGU7IHMpIFx1YzdhY1x1YzBkZFx1YjQxYyBcdWM3NGNcdWM1NDVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0PFwvcD5cclxuXHJcbjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmU0XHVjNzRjIFx1YzE1NFx1ZDUwY1x1Yzc3NCBcdWM1YjRcdWI1YmJcdWFjOGMgXHViNDE4XHViMjk0IFx1YzljMCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHVhYzAwIFx1YzVjNlx1YjJlNFx1YmE3NCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNjg5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU2h1ZmZsZSIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBsaXN0ZW5pbmcgdG8geW91ciBtdXNpYyBjb2xsZWN0aW9uIHVzaW5nIHRoZSBzaHVmZmxlIGZ1bmN0aW9uIHRvIGtlZXAgdGhlIG11c2ljIHN1cnByaXNpbmcuIFlvdSBhc3N1bWUgdGhhdCB0aGUgc2h1ZmZsZSBhbGdvcml0aG0gb2YgeW91ciBtdXNpYyBwbGF5ZXIgbWFrZXMgYSByYW5kb20gcGVybXV0YXRpb24gb2YgdGhlIHNvbmdzIGluIHRoZSBwbGF5bGlzdCBhbmQgcGxheXMgdGhlIHNvbmdzIGluIHRoYXQgb3JkZXIgdW50aWwgYWxsIHNvbmdzIGhhdmUgYmVlbiBwbGF5ZWQuIFRoZW4gaXQgcmVzaHVmZmxlcyBhbmQgc3RhcnRzIHBsYXlpbmcgdGhlIGxpc3QgYWdhaW4uPFwvcD5cclxuXHJcbjxwPllvdSBoYXZlIGEgaGlzdG9yeSBvZiB0aGUgc29uZ3MgdGhhdCBoYXZlIGJlZW4gcGxheWVkLiBIb3dldmVyLCB5b3VyIHJlY29yZCBvZiB0aGUgaGlzdG9yeSBvZiBwbGF5ZWQgc29uZ3MgaXMgbm90IGNvbXBsZXRlLCBhcyB5b3Ugc3RhcnRlZCByZWNvcmRpbmcgc29uZ3MgYXQgYSBjZXJ0YWluIHBvaW50IGluIHRpbWUgYW5kIGEgbnVtYmVyIG9mIHNvbmdzIG1pZ2h0IGFscmVhZHkgaGF2ZSBiZWVuIHBsYXllZC4gRnJvbSB0aGlzIGhpc3RvcnksIHlvdSB3YW50IHRvIGtub3cgYXQgaG93IG1hbnkgZGlmZmVyZW50IHBvaW50cyBpbiB0aGUgZnV0dXJlIHRoZSBuZXh0IHJlc2h1ZmZsZSBtaWdodCBvY2N1ci48XC9wPlxyXG5cclxuPHA+QSBwb3RlbnRpYWwgZnV0dXJlIHJlc2h1ZmZsZSBwb3NpdGlvbiBpcyB2YWxpZCBpZiBpdCBkaXZpZGVzIHRoZSByZWNvcmRlZCBoaXN0b3J5IGludG8gaW50ZXJ2YWxzIG9mIGxlbmd0aCBzICh0aGUgbnVtYmVyIG9mIHNvbmdzIGluIHRoZSBwbGF5bGlzdCkgd2l0aCB0aGUgZmlyc3QgYW5kIGxhc3QgaW50ZXJ2YWwgcG9zc2libHkgY29udGFpbmluZyBsZXNzIHRoYW4gcyBzb25ncyBhbmQgbm8gaW50ZXJ2YWwgY29udGFpbnMgYSBzcGVjaWZpYyBzb25nIG1vcmUgdGhhbiBvbmNlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0Y2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0Y2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIHR3byBpbnRlZ2VycyBzIGFuZCBuICgxICZsZTsgcywgbiAmbGU7IDEwMCAwMDApOiB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBzb25ncyBpbiB0aGUgcGxheWxpc3QgYW5kIHRoZSBudW1iZXIgb2Ygc29uZ3MgaW4gdGhlIHJlY29yZGVkIHBsYXlsaXN0IGhpc3RvcnkuPFwvbGk+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggbiBzcGFjZSBzZXBhcmF0ZWQgaW50ZWdlcnMsIHg8c3ViPjE8XC9zdWI+LCB4PHN1Yj4yPFwvc3ViPiwgLiAuIC4gLCB4PHN1Yj5uPFwvc3ViPiAoMSAmbGU7IHg8c3ViPmk8XC9zdWI+ICZsZTsgcyk6IHRoZSByZWNvcmRlZCBwbGF5bGlzdCBoaXN0b3J5PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCB0aGUgbnVtYmVyIG9mIGZ1dHVyZSBwb3NpdGlvbnMgdGhlIG5leHQgcmVzaHVmZmxlIGNhbiBiZSBhdC4gSWYgdGhlIGhpc3RvcnkgY291bGQgbm90IGJlIGdlbmVyYXRlZCBieSB0aGUgYWJvdmUgbWVudGlvbmVkIGFsZ29yaXRobSwgb3V0cHV0IDAuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=