시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 13 7 7 58.333%

문제

힙찌리 쇼미충 정주경은 음악 듣는 것을 좋아한다. 주경이는 음악을 들을 때 음악 플레이어의 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+XHJcblxyXG48cD5cdWQ1MGNcdWI4MDhcdWM3NzQgXHViOWFjXHVjMmE0XHVkMmI4XHVjNzU4IFx1Yzc0Y1x1YzU0NVx1Yzc1OCBcdWMyMThcdWI5N2Mgc1x1Yjc3YyBcdWQ1NjAmbmJzcDtcdWI1NGMmbmJzcDtcdWM3NGNcdWM1NDUgXHVjN2FjXHVjMGRkIFx1YmFhOVx1Yjg1ZFx1Yzc0NCBcdWFlMzhcdWM3NzQgc1x1Yzc3OCBcdWFkNmNcdWFjMDRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjBjIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1Y2M5OFx1Yzc0Y1x1YWNmYyBcdWI5YzhcdWM5YzBcdWI5YzkgXHVhZDZjXHVhYzA0XHVjNzQwIHNcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzhjXHViMDU0IFx1YjA5OFx1YjIwY1x1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWI1NGMgXHVhYzAxIFx1YWQ2Y1x1YWMwNFx1Yzc1OCBcdWM3NGNcdWM1NDVcdWM3NDAgXHVhY2I5XHVjY2QwXHVjMTFjXHViMjk0IFx1YzU0OFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2Q1Y1x1YjMwMCAxMDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWM3NzRcdWQ2YzQgXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IHNcdWM2NDAgbigxICZsZTsgcywgbiAmbGU7IDEwMCAwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gc1x1YjI5NCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWI5YWNcdWMyYTRcdWQyYjhcdWM3NTggXHVhY2UxXHVjNzU4Jm5ic3A7XHVjMjE4XHVjNzc0XHVhY2UwLCBuXHVjNzQwIFx1Yzc3NFx1YzgxY1x1YWVjZiZuYnNwO1x1YzdhY1x1YzBkZFx1YjQxYyZuYnNwO1x1YWNlMSZuYnNwO1x1YmFhOVx1Yjg1ZFx1Yzc1OCBcdWFjZTFcdWM3NTggXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IG5cdWFjMWNcdWM3NTgmbmJzcDt4MSwgeDIsIC4gLiAuICwgeG4mbmJzcDsoMSAmbGU7IHhpJm5ic3A7JmxlOyBzKSBcdWM3YWNcdWMwZGRcdWI0MWMgXHVjNzRjXHVjNTQ1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNDxcL3A+XHJcblxyXG48cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjJlNFx1Yzc0YyBcdWMxNTRcdWQ1MGNcdWM3NzQgXHVjNWI0XHViNWJiXHVhYzhjIFx1YjQxOFx1YjI5NCBcdWM5YzAgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM1YzZcdWIyZTRcdWJhNzQgMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzY4OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNodWZmbGUiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgbGlzdGVuaW5nIHRvIHlvdXIgbXVzaWMgY29sbGVjdGlvbiB1c2luZyB0aGUgc2h1ZmZsZSBmdW5jdGlvbiB0byBrZWVwIHRoZSBtdXNpYyBzdXJwcmlzaW5nLiBZb3UgYXNzdW1lIHRoYXQgdGhlIHNodWZmbGUgYWxnb3JpdGhtIG9mIHlvdXIgbXVzaWMgcGxheWVyIG1ha2VzIGEgcmFuZG9tIHBlcm11dGF0aW9uIG9mIHRoZSBzb25ncyBpbiB0aGUgcGxheWxpc3QgYW5kIHBsYXlzIHRoZSBzb25ncyBpbiB0aGF0IG9yZGVyIHVudGlsIGFsbCBzb25ncyBoYXZlIGJlZW4gcGxheWVkLiBUaGVuIGl0IHJlc2h1ZmZsZXMgYW5kIHN0YXJ0cyBwbGF5aW5nIHRoZSBsaXN0IGFnYWluLjxcL3A+XHJcblxyXG48cD5Zb3UgaGF2ZSBhIGhpc3Rvcnkgb2YgdGhlIHNvbmdzIHRoYXQgaGF2ZSBiZWVuIHBsYXllZC4gSG93ZXZlciwgeW91ciByZWNvcmQgb2YgdGhlIGhpc3Rvcnkgb2YgcGxheWVkIHNvbmdzIGlzIG5vdCBjb21wbGV0ZSwgYXMgeW91IHN0YXJ0ZWQgcmVjb3JkaW5nIHNvbmdzIGF0IGEgY2VydGFpbiBwb2ludCBpbiB0aW1lIGFuZCBhIG51bWJlciBvZiBzb25ncyBtaWdodCBhbHJlYWR5IGhhdmUgYmVlbiBwbGF5ZWQuIEZyb20gdGhpcyBoaXN0b3J5LCB5b3Ugd2FudCB0byBrbm93IGF0IGhvdyBtYW55IGRpZmZlcmVudCBwb2ludHMgaW4gdGhlIGZ1dHVyZSB0aGUgbmV4dCByZXNodWZmbGUgbWlnaHQgb2NjdXIuPFwvcD5cclxuXHJcbjxwPkEgcG90ZW50aWFsIGZ1dHVyZSByZXNodWZmbGUgcG9zaXRpb24gaXMgdmFsaWQgaWYgaXQgZGl2aWRlcyB0aGUgcmVjb3JkZWQgaGlzdG9yeSBpbnRvIGludGVydmFscyBvZiBsZW5ndGggcyAodGhlIG51bWJlciBvZiBzb25ncyBpbiB0aGUgcGxheWxpc3QpIHdpdGggdGhlIGZpcnN0IGFuZCBsYXN0IGludGVydmFsIHBvc3NpYmx5IGNvbnRhaW5pbmcgbGVzcyB0aGFuIHMgc29uZ3MgYW5kIG5vIGludGVydmFsIGNvbnRhaW5zIGEgc3BlY2lmaWMgc29uZyBtb3JlIHRoYW4gb25jZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCB0d28gaW50ZWdlcnMgcyBhbmQgbiAoMSAmbGU7IHMsIG4gJmxlOyAxMDAgMDAwKTogdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgc29uZ3MgaW4gdGhlIHBsYXlsaXN0IGFuZCB0aGUgbnVtYmVyIG9mIHNvbmdzIGluIHRoZSByZWNvcmRlZCBwbGF5bGlzdCBoaXN0b3J5LjxcL2xpPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIG4gc3BhY2Ugc2VwYXJhdGVkIGludGVnZXJzLCB4PHN1Yj4xPFwvc3ViPiwgeDxzdWI+MjxcL3N1Yj4sIC4gLiAuICwgeDxzdWI+bjxcL3N1Yj4gKDEgJmxlOyB4PHN1Yj5pPFwvc3ViPiAmbGU7IHMpOiB0aGUgcmVjb3JkZWQgcGxheWxpc3QgaGlzdG9yeTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggdGhlIG51bWJlciBvZiBmdXR1cmUgcG9zaXRpb25zIHRoZSBuZXh0IHJlc2h1ZmZsZSBjYW4gYmUgYXQuIElmIHRoZSBoaXN0b3J5IGNvdWxkIG5vdCBiZSBnZW5lcmF0ZWQgYnkgdGhlIGFib3ZlIG1lbnRpb25lZCBhbGdvcml0aG0sIG91dHB1dCAwLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d