시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 46 29 26 60.465%

문제

상근이는 라스베가스의 엘 도라도 카지노에 도착했다. 태어나서 카지노에 처음 가본 상근이는 휘황찬란한 카지노의 내부에 입을 다물 수 없었다. 그런 그의 눈길을 사로 잡는 게임이 하나있었다. 그 게임은 화면에 n개의 숫자가 화면에 뜨는 아주 단순해 보이는 게임이었다. 이 게임의 참가자는 컴퓨터가 만드는 수열에서 길이가 k인 증가하는 부분 수열의 개수를 예상해야 한다.

수열 a1, ..., an의 부분 수열은 1 ≤ i1 < i2 < ... < il ≤ n를 만족하는 ai1, ..., ail로 정의 한다. 부분 수열이 증가하려면 모든 1 < j ≤ l에 대해서, aij-1 < aij를 만족해야 한다.

상근이는 다른 사람이 작성한 프로그램을 믿지 않는다. 따라서, 기계에 표시된 정답 대신 자신이 직접 정답을 구해 보려고 한다. 기계의 화면에 표시된 숫자가 주어졌을 때, 길이가 k이면서 증가하는 부분 수열의 개수를 세는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n과 k가 주어진다. (1 ≤ k ≤ n ≤ 100) 둘째 줄에는 컴퓨터가 만든 수열 ai가 주어진다. ai는 서로 중복되지 않는다. (-10000 ≤ ai ≤ 10000)

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각각의 테스트 케이스에 대해서, 길이가 k인 증가하는 부분 수열의 개수를 출력한다. 이 값은 64비트 정수 범위를 넘지 않는다.

예제 입력 1

10 5
1 2 3 4 5 6 7 8 9 10
3 2
3 2 1
0 0

예제 출력 1

252
0
W3sicHJvYmxlbV9pZCI6IjY1MDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZDggXHViM2M0XHViNzdjXHViM2M0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViNzdjXHVjMmE0XHViY2EwXHVhYzAwXHVjMmE0XHVjNzU4IFx1YzVkOCBcdWIzYzRcdWI3N2NcdWIzYzQgXHVjZTc0XHVjOWMwXHViMTc4XHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU4OFx1YjJlNC4gXHVkMGRjXHVjNWI0XHViMDk4XHVjMTFjIFx1Y2U3NFx1YzljMFx1YjE3OFx1YzVkMCBcdWNjOThcdWM3NGMgXHVhYzAwXHViY2Y4IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQ3MThcdWQ2NjlcdWNjMmNcdWI3ODBcdWQ1NWMgXHVjZTc0XHVjOWMwXHViMTc4XHVjNzU4IFx1YjBiNFx1YmQ4MFx1YzVkMCBcdWM3ODVcdWM3NDQgXHViMmU0XHViYjNjIFx1YzIxOCBcdWM1YzZcdWM1YzhcdWIyZTQuIFx1YWRmOFx1YjdmMCBcdWFkZjhcdWM3NTggXHViMjA4XHVhZTM4XHVjNzQ0IFx1YzBhY1x1Yjg1YyBcdWM3YTFcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzc0IFx1ZDU1OFx1YjA5OFx1Yzc4OFx1YzVjOFx1YjJlNC4gXHVhZGY4IFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWQ2NTRcdWJhNzRcdWM1ZDAgblx1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVkNjU0XHViYTc0XHVjNWQwIFx1YjcyOFx1YjI5NCBcdWM1NDRcdWM4ZmMgXHViMmU4XHVjMjFjXHVkNTc0IFx1YmNmNFx1Yzc3NFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzRcdWM1YzhcdWIyZTQuIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NTggXHVjYzM4XHVhYzAwXHVjNzkwXHViMjk0IFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1YWMwMCBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjIFx1YWUzOFx1Yzc3NFx1YWMwMCBrXHVjNzc4IFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWM2MDhcdWMwYzFcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWM1ZjQgYTxzdWI+MTxcL3N1Yj4sIC4uLiwgYTxzdWI+bjxcL3N1Yj5cdWM3NTggXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc0MCAxICZsZTsgaTxzdWI+MTxcL3N1Yj4gJmx0OyBpPHN1Yj4yPFwvc3ViPiAmbHQ7IC4uLiAmbHQ7IGk8c3ViPmw8XC9zdWI+ICZsZTsgblx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgYTxzdWI+aTE8XC9zdWI+LCAuLi4sIGE8c3ViPmlsPFwvc3ViPlx1Yjg1YyBcdWM4MTVcdWM3NTggXHVkNTVjXHViMmU0LiBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjgyNFx1YmE3NCBcdWJhYThcdWI0ZTAgMSAmbHQ7IGogJmxlOyBsXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgYTxzdWI+aWotMTxcL3N1Yj4gJmx0OyBhPHN1Yj5pajxcL3N1Yj5cdWI5N2MgXHViOWNjXHVjODcxXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjJlNFx1Yjk3OCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNzkxXHVjMTMxXHVkNTVjIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWJiZmZcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YWUzMFx1YWNjNFx1YzVkMCBcdWQ0NWNcdWMyZGNcdWI0MWMgXHVjODE1XHViMmY1IFx1YjMwMFx1YzJlMCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjOWMxXHVjODExIFx1YzgxNVx1YjJmNVx1Yzc0NCBcdWFkNmNcdWQ1NzQgXHViY2Y0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhZTMwXHVhY2M0XHVjNzU4IFx1ZDY1NFx1YmE3NFx1YzVkMCBcdWQ0NWNcdWMyZGNcdWI0MWMgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWUzOFx1Yzc3NFx1YWMwMCBrXHVjNzc0XHViYTc0XHVjMTFjIFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWMxMzhcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBuXHVhY2ZjIGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IGsgJmxlOyBuICZsZTsgMTAwKSBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1YWMwMCBcdWI5Y2NcdWI0ZTAgXHVjMjE4XHVjNWY0IGE8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gYTxzdWI+aTxcL3N1Yj5cdWIyOTQgXHVjMTFjXHViODVjIFx1YzkxMVx1YmNmNVx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuICgtMTAwMDAgJmxlOyBhPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDAwKTxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YjQ1MCBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhZTM4XHVjNzc0XHVhYzAwIGtcdWM3NzggXHVjOTlkXHVhYzAwXHVkNTU4XHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YWMxMlx1Yzc0MCA2NFx1YmU0NFx1ZDJiOCBcdWM4MTVcdWMyMTggXHViYzk0XHVjNzA0XHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjUwNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVsIERvcmFkbyIsImRlc2NyaXB0aW9uIjoiPHA+QnJ1Y2UgRm9yY2UgaGFzIGdvbmUgdG8gTGFzIFZlZ2FzLCB0aGUgRWwgRG9yYWRvIGZvciBnYW1ibGVycy4gSGUgaXMgaW50ZXJlc3RlZCBlc3BlY2lhbGx5IGluIG9uZSBiZXR0aW5nIGdhbWUsIHdoZXJlIGEgbWFjaGluZSBmb3JtcyBhIHNlcXVlbmNlIG9mIG4gbnVtYmVycyBieSBkcmF3aW5nIHJhbmRvbSBudW1iZXJzLiBFYWNoIHBsYXllciBzaG91bGQgZXN0aW1hdGUgYmVmb3JlaGFuZCwgaG93IG1hbnkgaW5jcmVhc2luZyBzdWJzZXF1ZW5jZXMgb2YgbGVuZ3RoIGsgd2lsbCBleGlzdCBpbiB0aGUgc2VxdWVuY2Ugb2YgbnVtYmVycy48XC9wPlxyXG5cclxuPHA+QSBzdWJzZXF1ZW5jZSBvZiBhIHNlcXVlbmNlIGE8c3ViPjE8XC9zdWI+LCAuLi4sIGE8c3ViPm48XC9zdWI+IGlzIGRlZmluZWQgYXMgYTxzdWI+aTE8XC9zdWI+LCAuLi4sIGE8c3ViPmlsPFwvc3ViPiwgd2hlcmUgMSAmbGU7IGk8c3ViPjE8XC9zdWI+ICZsdDsgaTIgJmx0OyAuLi4gJmx0OyBpbCAmbGU7IG4uIFRoZSBzdWJzZXF1ZW5jZSBpcyBpbmNyZWFzaW5nLCBpZiBhPHN1Yj5pai0xPFwvc3ViPiAmbHQ7IGE8c3ViPmlqPFwvc3ViPiBmb3IgYWxsIDEgJmx0OyBqICZsZTsgbC48XC9wPlxyXG5cclxuPHA+QnJ1Y2UgZG9lc24mIzM5O3QgdHJ1c3QgdGhlIENhc2lubyB0byBjb3VudCB0aGUgbnVtYmVyIG9mIGluY3JlYXNpbmcgc3Vic2VxdWVuY2VzIG9mIGxlbmd0aCBrIGNvcnJlY3RseS4gSGUgaGFzIGFza2VkIHlvdSBpZiB5b3UgY2FuIHNvbHZlIHRoaXMgcHJvYmxlbSBmb3IgaGltLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIHNldmVyYWwgdGVzdCBjYXNlcy4gVGhlIGZpcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2UgY29udGFpbnMgdHdvIG51bWJlcnMgbiBhbmQgayAoMSAmbGU7IGsgJmxlOyBuICZsZTsgMTAwKSwgd2hlcmUgbiBpcyB0aGUgbGVuZ3RoIG9mIHRoZSBzZXF1ZW5jZSBkcmF3biBieSB0aGUgbWFjaGluZSwgYW5kIGsgaXMgdGhlIGRlc2lyZWQgbGVuZ3RoIG9mIHRoZSBpbmNyZWFzaW5nIHN1YnNlcXVlbmNlcy4gVGhlIGZvbGxvd2luZyBsaW5lIGNvbnRhaW5zIG4gcGFpcndpc2UgZGlzdGluY3QgaW50ZWdlcnMgYTxzdWI+aTxcL3N1Yj4gKC0xMDAwMCAmbGU7IGE8c3ViPmk8XC9zdWI+ICZsZTsgMTAwMDAgKSwgd2hlcmUgYWkgaXMgdGhlIGl0aCBudW1iZXIgaW4gdGhlIHNlcXVlbmNlIGRyYXduIGJ5IHRoZSBtYWNoaW5lLjxcL3A+XHJcblxyXG48cD5UaGUgbGFzdCB0ZXN0IGNhc2UgaXMgZm9sbG93ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgdHdvIHplcm9zLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgb25lIGxpbmUgd2l0aCB0aGUgbnVtYmVyIG9mIGluY3JlYXNpbmcgc3Vic2VxdWVuY2VzIG9mIGxlbmd0aCBrIHRoYXQgdGhlIGlucHV0IHNlcXVlbmNlIGNvbnRhaW5zLiBZb3UgbWF5IGFzc3VtZSB0aGF0IHRoZSBpbnB1dHMgYXJlIGNob3NlbiBpbiBzdWNoIGEgd2F5IHRoYXQgdGhpcyBudW1iZXIgZml0cyBpbnRvIGEgNjQgYml0IHNpZ25lZCBpbnRlZ2VyIChpbiBDXC9DKyssIHlvdSBtYXkgdXNlIHRoZSBkYXRhIHR5cGUgJnF1b3Q7bG9uZyBsb25nJnF1b3Q7LCBpbiBKYXZhIHRoZSBkYXRhIHR5cGUgJnF1b3Q7bG9uZyZxdW90OykuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d