시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 17 8 4 33.333%

문제

이번 문제에서 크기가 k인 알파벳이란, 아래와 같은 리스트에서 처음 k개의 글자를 말한다.

a, b, c, ... , z, A, B, C, ... , Z, 0, 1, ... , 9.

각각의 테스트 케이스마다 k가 주어지며, 크기가 k인 알파벳만 고려한다.

문자열 t[1..m]이 문자열 s[1..n]의 부분 수열이 되려면, t[1] = s[i1], t[2] = s[i2], ..., t[m] = t[im]을 만족하는 인덱스 1 ≤ i1 < i2 <... im ≤ n가 존재해야 한다. 예를 들어, acb는 babcaab의 부분 수열이다.

문자열 s[1..n]이 주어졌을 때, s의 부분 수열이 아닌 문자열 t[1..m] 중에서 m 값이 가장 작은 것을 찾고, 그러한 문자열의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t ≤ 100이 주어진다. 각각의 테스트 케이스는 알파벳의 크기 k (k ∈ [1, 62])와 문자열 s[1..n] (n ∈ [1, 106])이 주어진다.

출력

각각의 테스트 케이스마다, 두 개의 정수를 출력한다. 첫 번째 정수는 가장 작은 m이고, 두 번째 정수는 가능한 문자열 t[1..m]의 개수를 109 + 7로 나눈 나머지이다.

예제 입력 1

3
2 abba
62 0123456789
3 aabbcbbcbabcbab

예제 출력 1

3 5
1 52
4 7
W3sicHJvYmxlbV9pZCI6IjEwMjc5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM1NDRcdWIyZDgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc3NFx1YmM4OCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVkMDZjXHVhZTMwXHVhYzAwIGtcdWM3NzggXHVjNTRjXHVkMzBjXHViY2IzXHVjNzc0XHViNzgwLCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YjlhY1x1YzJhNFx1ZDJiOFx1YzVkMFx1YzExYyBcdWNjOThcdWM3NGMga1x1YWMxY1x1Yzc1OCBcdWFlMDBcdWM3OTBcdWI5N2MgXHViOWQwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+YSwgYiwgYywgLi4uICwgeiwgQSwgQiwgQywgLi4uICwgWiwgMCwgMSwgLi4uICwgOS48XC9wPlxyXG5cclxuPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1ZDA2Y1x1YWUzMFx1YWMwMCBrXHVjNzc4IFx1YzU0Y1x1ZDMwY1x1YmNiM1x1YjljYyBcdWFjZTBcdWI4MjRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1Yzc5MFx1YzVmNCB0WzEuLm1dXHVjNzc0IFx1YmIzOFx1Yzc5MFx1YzVmNCBzWzEuLm5dXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NzQgXHViNDE4XHViODI0XHViYTc0LCB0WzFdID0gc1tpPHN1Yj4xPFwvc3ViPl0sIHRbMl0gPSBzW2k8c3ViPjI8XC9zdWI+XSwgLi4uLCB0W21dID0gdFtpPHN1Yj5tPFwvc3ViPl1cdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1Yzc3OFx1YjM3MVx1YzJhNCAxICZsZTsgaTxzdWI+MTxcL3N1Yj4mbmJzcDsmbHQ7IGk8c3ViPjI8XC9zdWI+Jm5ic3A7Jmx0Oy4uLiBpPHN1Yj5tPFwvc3ViPiZuYnNwOyZsZTsgblx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBhY2JcdWIyOTQgYmFiY2FhYlx1Yzc1OCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM3OTBcdWM1ZjQgc1sxLi5uXVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBzXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YmIzOFx1Yzc5MFx1YzVmNCB0WzEuLm1dIFx1YzkxMVx1YzVkMFx1YzExYyBtIFx1YWMxMlx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWNjM2VcdWFjZTAsIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCB0ICZsZTsgMTAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzU4IFx1ZDA2Y1x1YWUzMCBrJm5ic3A7KGsgJmlzaW47IFsxLCA2Ml0pXHVjNjQwIFx1YmIzOFx1Yzc5MFx1YzVmNCBzWzEuLm5dJm5ic3A7KG4gJmlzaW47IFsxLCAxMDxzdXA+NjxcL3N1cD5dKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQsIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM4MTVcdWMyMThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBtXHVjNzc0XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViYjM4XHVjNzkwXHVjNWY0IHRbMS4ubV1cdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjJm5ic3A7MTA8c3VwPjk8XC9zdXA+Jm5ic3A7KyA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTAyNzkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJOb3QgYSBzdWJzZXF1ZW5jZSIsImRlc2NyaXB0aW9uIjoiPHA+SW4gdGhpcyBwcm9ibGVtIHdlIGNvbnNpZGVyIHN0cmluZ3Mgb3ZlciBhIGZpeGVkIGZpbml0ZSBhbHBoYWJldCBvZiBzaXplIGsuIFRoZSBhbHBoYWJldCBjb250YWlucyB0aGUgZmlyc3QgayBjaGFyYWN0ZXJzIGZyb20gdGhlIGxpc3Q8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+YSwgYiwgYywgLi4uICwgeiwgQSwgQiwgQywgLi4uICwgWiwgMCwgMSwgLi4uICwgOS48XC9wPlxyXG5cclxuPHA+Rm9yIGV2ZXJ5IHRlc3QgY2FzZSwgd2UgYXJlIGdpdmVuIHRoZSB2YWx1ZSBvZiBrIChub3RpY2UgdGhhdCBpdCBjYW5ub3QgZXhjZWVkIDYyKSwgYW5kIGNvbnNpZGVyIG9ubHkgc3RyaW5ncyBjb25zaXN0aW5nIG9mIHRoZSBmaXJzdCBrIGNoYXJhY3RlcnMgZnJvbSB0aGUgbGlzdC48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBzdHJpbmcgc1sxLi5uXSwgd2UgYXJlIGludGVyZXN0ZWQgaW4gc3RyaW5ncyB3aGljaCBhcmUgbm90IGl0cyBzdWJzZXF1ZW5jZXMuIEZvcm1hbGx5LCBhIHN0cmluZyB0WzEuLm1dIGlzIGEgc3Vic2VxdWVuY2Ugb2YgYSBzdHJpbmcgc1sxLi5uXSB3aGVuIG9uZSBjYW4gY2hvb3NlIG5vdCBuZWNlc3NhcmlseSBjb250aWd1b3VzIGluZGljZXMgMSAmbGU7IGk8c3ViPjE8XC9zdWI+ICZsdDsgaTxzdWI+MjxcL3N1Yj4gJmx0Oy4uLiBpPHN1Yj5tPFwvc3ViPiAmbGU7IG4gc3VjaCB0aGF0IHRbMV0gPSBzW2k8c3ViPjE8XC9zdWI+XSwgdFsyXSA9IHNbaTxzdWI+MjxcL3N1Yj5dLCAuLi4sIHRbbV0gPSB0W2k8c3ViPm08XC9zdWI+XS4gRm9yIGV4YW1wbGUsIGFjYiBpcyBhIHN1YnNlcXVlbmNlIG9mIGJhYmNhYWIuIE5vdywgZ2l2ZW4gYSBzdHJpbmcgc1sxLi5uXSwgd2Ugd291bGQgbGlrZSB0byBjb21wdXRlIHRoZSBzbWFsbGVzdCBtIHN1Y2ggdGhhdCB0aGVyZSBpcyBhIHN0cmluZyB0WzEuLm1dLCB3aGljaCBpcyBub3QgYSBzdWJzZXF1ZW5jZSBvZiBzWzEuLm5dLiBBZGRpdGlvbmFsbHksIHdlIHdvdWxkIGxpa2UgdG8gY291bnQgdGhlIG51bWJlciBvZiBzdWNoIHNob3J0ZXN0IHN0cmluZ3MgdFsxLi5tXS4gQXMgdGhlIGxhdHRlciBudW1iZXIgY2FuIGJlIHF1aXRlIGxhcmdlLCBvdXRwdXQgaXQgbW9kdWxvIDEwPHN1cD45PFwvc3VwPiArIDcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgc3RhcnRzIHdpdGggdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgJmxlOyAxMDAuIFRoZW4gdGhlIGRlc2NyaXB0aW9ucyBvZiBUIHRlc3QgY2FzZXMgZm9sbG93LiBBIHNpbmdsZSB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRoZSBzaXplIG9mIHRoZSBhbHBoYWJldCBrIChrICZpc2luOyBbMSwgNjJdKSBhbmQgdGhlIHN0cmluZyBzWzEuLm5dIChuICZpc2luOyBbMSwgMTA8c3VwPjY8XC9zdXA+XSkuIFRoZSBzdHJpbmcgY29uc2lzdHMgb2YgdGhlIGZpcnN0IGsgY2hhcmFjdGVycyBmcm9tIGEmbmRhc2g7ekEmbmRhc2g7WjAmbmRhc2g7OS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZXZlcnkgdGVzdCBjYXNlIG91dHB1dCBvbmUgbGluZSBjb250YWluaW5nIHR3byBudW1iZXJzLiBUaGUgZmlyc3QgbnVtYmVyIGlzIHRoZSBzbWFsbGVzdCBtIHN1Y2ggdGhhdCB0aGVyZSBpcyBhIHN0cmluZyB0WzEuLm1dIGNvbnNpc3Rpbmcgb2YgdGhlIGZpcnN0IGsgY2hhcmFjdGVycyBmcm9tIGEmbmRhc2g7ekEmbmRhc2g7WjAmbmRhc2g7OSwgd2hpY2ggaXMgbm90IGEgc3Vic2VxdWVuY2Ugb2Ygc1sxLi5uXS4gVGhlIHNlY29uZCBudW1iZXIgaXMgdGhlIHRvdGFsIGNvdW50IG9mIHN1Y2ggc2hvcnRlc3Qgc3RyaW5ncyB0WzEuLm1dIG1vZHVsbyAxMDxzdXA+OTxcL3N1cD4gKyA3LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==