시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 304 147 107 44.033%

문제

상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?

예를 들어, 카드가 5장 있고, 카드에 써 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만드려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러가지 일 수 있다.

n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이, 둘째 줄에 k가 주어진다. 셋째 줄부터 n개 줄에는 카드에 적혀있는 수가 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 정수의 개수를 출력한다.

예제 입력 1

4
2
1
2
12
1

예제 출력 1

7

힌트

상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다.

W3sicHJvYmxlbV9pZCI6IjU1NjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlNzRcdWI0ZGMgXHViMTkzXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjZTc0XHViNGRjIG4oNCAmbGU7IG4gJmxlOyAxMClcdWM3YTVcdWM3NDQgXHViYzE0XHViMmU1XHVjNWQwIFx1YjA5OFx1Yjc4MFx1ZDc4OCBcdWIxOTNcdWFjZTAgXHViMTgwXHVhY2UwXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjZTc0XHViNGRjXHVjNWQwXHViMjk0IDFcdWM3NzRcdWMwYzEgOTlcdWM3NzRcdWQ1NThcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YzgwMVx1ZDYwMFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzQgXHVjZTc0XHViNGRjIFx1YzkxMVx1YzVkMFx1YzExYyBrKDIgJmxlOyBrICZsZTsgNClcdWM3YTVcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTU4XHVhY2UwLCBcdWFjMDBcdWI4NWNcdWI4NWMgXHViMDk4XHViNzgwXHVkNzg4IFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjODE1XHVjMjE4XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWJhODcgXHVhYzAwXHVjOWMwXHVjNzdjXHVhZTRjPzxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWNlNzRcdWI0ZGNcdWFjMDAgNVx1YzdhNSBcdWM3ODhcdWFjZTAsIFx1Y2U3NFx1YjRkY1x1YzVkMCBcdWMzNjggXHVjNzg4XHViMjk0IFx1YzIxOFx1YWMwMCAxLCAyLCAzLCAxMywgMjFcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWM1ZWNcdWFlMzBcdWMxMWMgM1x1YzdhNVx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NzRcdWMxMWMgXHVjODE1XHVjMjE4XHViOTdjIFx1YjljY1x1YjRkY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIDIsIDEsIDEzXHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWIwOThcdWM1ZjRcdWQ1NThcdWJhNzQgXHVjODE1XHVjMjE4IDIxMTNcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgMjEsIDEsIDNcdWM3NDQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YjA5OFx1YzVmNFx1ZDU1OFx1YmE3NCAyMTEzXHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVkNTVjIFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjODcwXHVkNTY5XHVjNzc0IFx1YzVlY1x1YjdlY1x1YWMwMFx1YzljMCBcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0blx1YzdhNVx1Yzc1OCBcdWNlNzRcdWI0ZGNcdWM1ZDAgXHVjODAxXHVkNzhjIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVjOTExXHVjNWQwXHVjMTFjIGtcdWFjMWNcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTc0XHVjMTFjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIG5cdWM3NzQsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZTc0XHViNGRjXHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgMTEsIDEyLCAyMSwgMTEyLCAxMjEsIDEyMiwgMjEyXHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTU2OCIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6Ilx1MzBhYlx1MzBmY1x1MzBjOVx1NGUyNlx1MzA3OSIsImRlc2NyaXB0aW9uIjoiPHA+XHU4MmIxXHU1YjUwXHUzMDU1XHUzMDkzXHUzMDZmIG4gXHU2NzlhXHVmZjA4NCBcdTIyNjYgbiBcdTIyNjYgMTBcdWZmMDlcdTMwNmVcdTMwYWJcdTMwZmNcdTMwYzlcdTMwOTJcdTRlMjZcdTMwNzlcdTMwNjZcdTkwNGFcdTMwOTNcdTMwNjdcdTMwNDRcdTMwOGJcdWZmMGUgXHUzMDVkXHUzMDhjXHUzMDVlXHUzMDhjXHUzMDZlXHUzMGFiXHUzMGZjXHUzMGM5XHUzMDZiXHUzMDZmIDEgXHU0ZWU1XHU0ZTBhIDk5IFx1NGVlNVx1NGUwYlx1MzA2ZVx1NjU3NFx1NjU3MFx1MzA0YyAxIFx1MzA2NFx1MzA1YVx1MzA2NFx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZSBcdTgyYjFcdTViNTBcdTMwNTVcdTMwOTNcdTMwNmZcdWZmMGNcdTMwNTNcdTMwOGNcdTMwODlcdTMwNmVcdTMwYWJcdTMwZmNcdTMwYzlcdTMwNmVcdTRlMmRcdTMwNGJcdTMwODkgayBcdTY3OWFcdWZmMDgyIFx1MjI2NiBrIFx1MjI2NiA0XHVmZjA5XHUzMDkyXHU5MDc4XHUzMDczXHVmZjBjIFx1NmEyYVx1NGUwMFx1NTIxN1x1MzA2Ylx1NGUyNlx1MzA3OVx1MzA2Nlx1NjU3NFx1NjU3MFx1MzA5Mlx1NGY1Y1x1MzA4Ylx1MzA1M1x1MzA2OFx1MzA2Ylx1MzA1N1x1MzA1Zlx1ZmYwZSBcdTgyYjFcdTViNTBcdTMwNTVcdTMwOTNcdTMwNmZcdTUxNjhcdTkwZThcdTMwNjdcdTRmNTVcdTdhMmVcdTk4NWVcdTMwNmVcdTY1NzRcdTY1NzBcdTMwOTJcdTRmNWNcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNGNcdTMwNjdcdTMwNGRcdTMwOGJcdTMwNjBcdTMwOGRcdTMwNDZcdTMwNGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU0ZjhiXHUzMDQ4XHUzMDcwXHVmZjBjMSwgMiwgMywgMTMsIDIxIFx1MzA2ZSA1IFx1Njc5YVx1MzA2ZVx1MzBhYlx1MzBmY1x1MzBjOVx1MzA0Y1x1NGUwZVx1MzA0OFx1MzA4OVx1MzA4Y1x1ZmYwY1x1MzA1ZFx1MzA1M1x1MzA0Ylx1MzA4OSAzIFx1Njc5YVx1MzA5Mlx1OTA3OFx1MzA3M1x1NjU3NFx1NjU3MFx1MzA5Mlx1NGY1Y1x1MzA4Ylx1MzA1M1x1MzA2OFx1MzA5Mlx1ODAwM1x1MzA0OFx1MzA4Ylx1ZmYwZSAyLCAxLCAxMyBcdTMwOTJcdTMwNTNcdTMwNmVcdTk4MDZcdTMwNmJcdTRlMjZcdTMwNzlcdTMwOGJcdTMwNjhcdWZmMGNcdTY1NzRcdTY1NzAgMjExMyBcdTMwOTJcdTRmNWNcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNGNcdTMwNjdcdTMwNGRcdTMwOGJcdWZmMGUgXHUzMDdlXHUzMDVmXHVmZjBjMjEsIDEsIDMgXHUzMDkyXHUzMDUzXHUzMDZlXHU5ODA2XHUzMDZiXHU0ZTI2XHUzMDc5XHUzMDY2XHUzMDgyXHVmZjBjXHU1NDBjXHUzMDU4XHU2NTc0XHU2NTcwIDIxMTMgXHUzMDkyXHU0ZjVjXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDRjXHUzMDY3XHUzMDRkXHUzMDhiXHVmZjBlIFx1MzA1M1x1MzA2ZVx1MzA4OFx1MzA0Nlx1MzA2Ylx1ZmYwY1x1NzU3MFx1MzA2YVx1MzA4Ylx1MzBhYlx1MzBmY1x1MzBjOVx1MzA2ZVx1N2Q0NFx1MzA3Zlx1NTQwOFx1MzA4Zlx1MzA1Ylx1MzA0Ylx1MzA4OVx1NTQwY1x1MzA1OFx1NjU3NFx1NjU3MFx1MzA0Y1x1NGY1Y1x1MzA4OVx1MzA4Y1x1MzA4Ylx1MzA1M1x1MzA2OFx1MzA4Mlx1MzA0Mlx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD5uIFx1Njc5YVx1MzA2ZVx1MzBhYlx1MzBmY1x1MzBjOVx1MzA2Ylx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA1Zlx1NjU3NFx1NjU3MFx1MzA0Y1x1NGUwZVx1MzA0OFx1MzA4OVx1MzA4Y1x1MzA1Zlx1MzA2OFx1MzA0ZFx1ZmYwYyBcdTMwNWRcdTMwNmVcdTRlMmRcdTMwNGJcdTMwODkgayBcdTY3OWFcdTMwOTJcdTkwNzhcdTMwNzNcdWZmMGNcdTZhMmFcdTRlMDBcdTUyMTdcdTMwNmJcdTRlMjZcdTMwNzlcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNjdcdTRmNWNcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNGNcdTMwNjdcdTMwNGRcdTMwOGJcdTY1NzRcdTY1NzBcdTMwNmVcdTUwMGJcdTY1NzBcdTMwOTJcdTZjNDJcdTMwODFcdTMwOGJcdTMwZDdcdTMwZWRcdTMwYjBcdTMwZTlcdTMwZTBcdTMwOTJcdTRmNWNcdTYyMTBcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1NTE2NVx1NTI5Ylx1MzA2ZiAyK24gXHU4ODRjXHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHVmZjBlIDEgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHUzMGFiXHUzMGZjXHUzMGM5XHUzMDZlXHU2NzlhXHU2NTcwIG4gXHVmZjA4NCBcdTIyNjYgbiBcdTIyNjYgMTBcdWZmMDlcdTMwNGNcdWZmMGMgMiBcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmZcdTMwYWJcdTMwZmNcdTMwYzlcdTMwOTJcdTkwNzhcdTMwNzZcdTY3OWFcdTY1NzAgayBcdWZmMDgyIFx1MjI2NiBrIFx1MjI2NiA0XHVmZjA5XHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlIDIraSBcdTg4NGNcdTc2ZWVcdWZmMDgxIFx1MjI2NiBpIFx1MjI2NiBuXHVmZjA5XHUzMDZiXHUzMDZmIGkgXHU2NzlhXHU3NmVlXHUzMDZlXHUzMGFiXHUzMGZjXHUzMGM5XHUzMDZiXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiIDEgXHU0ZWU1XHU0ZTBhIDk5IFx1NGVlNVx1NGUwYlx1MzA2ZVx1NjU3NFx1NjU3MFx1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdTUxZmFcdTUyOWJcdTMwNmZcdWZmMGNcdTgyYjFcdTViNTBcdTMwNTVcdTMwOTNcdTMwNGNcdTRmNWNcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNGNcdTMwNjdcdTMwNGRcdTMwOGJcdTY1NzRcdTY1NzBcdTMwNmVcdTUwMGJcdTY1NzBcdTMwNmVcdTMwN2ZcdTMwOTJcdTU0MmJcdTMwODAgMSBcdTg4NGNcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNzdjXHViY2Y4XHVjNWI0In1d