시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 368 171 128 42.809%

문제

상근이는 카드 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+XHJcblxyXG48cD5cclxuXHRcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWNlNzRcdWI0ZGNcdWFjMDAgNVx1YzdhNSBcdWM3ODhcdWFjZTAsIFx1Y2U3NFx1YjRkY1x1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzIxOFx1YWMwMCAxLCAyLCAzLCAxMywgMjFcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWM1ZWNcdWFlMzBcdWMxMWMgM1x1YzdhNVx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NzRcdWMxMWMgXHVjODE1XHVjMjE4XHViOTdjIFx1YjljY1x1YjRkY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIDIsIDEsIDEzXHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWIwOThcdWM1ZjRcdWQ1NThcdWJhNzQgXHVjODE1XHVjMjE4IDIxMTNcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgMjEsIDEsIDNcdWM3NDQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YjA5OFx1YzVmNFx1ZDU1OFx1YmE3NCAyMTEzXHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVkNTVjIFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjODcwXHVkNTY5XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzAgXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdG5cdWM3YTVcdWM3NTggXHVjZTc0XHViNGRjXHVjNWQwIFx1YzgwMVx1ZDc4YyBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhZGY4IFx1YzkxMVx1YzVkMFx1YzExYyBrXHVhYzFjXHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBuXHVjNzc0LCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMxNGJcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2U3NFx1YjRkY1x1YzVkMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHJcblx0XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IDExLCAxMiwgMjEsIDExMiwgMTIxLCAxMjIsIDIxMlx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU1NjgiLCJwcm9ibGVtX2xhbmciOiIyIiwidGl0bGUiOiJcdTMwYWJcdTMwZmNcdTMwYzlcdTRlMjZcdTMwNzkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ODJiMVx1NWI1MFx1MzA1NVx1MzA5M1x1MzA2ZiBuIFx1Njc5YVx1ZmYwODQgXHUyMjY2IG4gXHUyMjY2IDEwXHVmZjA5XHUzMDZlXHUzMGFiXHUzMGZjXHUzMGM5XHUzMDkyXHU0ZTI2XHUzMDc5XHUzMDY2XHU5MDRhXHUzMDkzXHUzMDY3XHUzMDQ0XHUzMDhiXHVmZjBlIFx1MzA1ZFx1MzA4Y1x1MzA1ZVx1MzA4Y1x1MzA2ZVx1MzBhYlx1MzBmY1x1MzBjOVx1MzA2Ylx1MzA2ZiAxIFx1NGVlNVx1NGUwYSA5OSBcdTRlZTVcdTRlMGJcdTMwNmVcdTY1NzRcdTY1NzBcdTMwNGMgMSBcdTMwNjRcdTMwNWFcdTMwNjRcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGUgXHU4MmIxXHU1YjUwXHUzMDU1XHUzMDkzXHUzMDZmXHVmZjBjXHUzMDUzXHUzMDhjXHUzMDg5XHUzMDZlXHUzMGFiXHUzMGZjXHUzMGM5XHUzMDZlXHU0ZTJkXHUzMDRiXHUzMDg5IGsgXHU2NzlhXHVmZjA4MiBcdTIyNjYgayBcdTIyNjYgNFx1ZmYwOVx1MzA5Mlx1OTA3OFx1MzA3M1x1ZmYwYyBcdTZhMmFcdTRlMDBcdTUyMTdcdTMwNmJcdTRlMjZcdTMwNzlcdTMwNjZcdTY1NzRcdTY1NzBcdTMwOTJcdTRmNWNcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNmJcdTMwNTdcdTMwNWZcdWZmMGUgXHU4MmIxXHU1YjUwXHUzMDU1XHUzMDkzXHUzMDZmXHU1MTY4XHU5MGU4XHUzMDY3XHU0ZjU1XHU3YTJlXHU5ODVlXHUzMDZlXHU2NTc0XHU2NTcwXHUzMDkyXHU0ZjVjXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDRjXHUzMDY3XHUzMDRkXHUzMDhiXHUzMDYwXHUzMDhkXHUzMDQ2XHUzMDRiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NGY4Ylx1MzA0OFx1MzA3MFx1ZmYwYzEsIDIsIDMsIDEzLCAyMSBcdTMwNmUgNSBcdTY3OWFcdTMwNmVcdTMwYWJcdTMwZmNcdTMwYzlcdTMwNGNcdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdWZmMGNcdTMwNWRcdTMwNTNcdTMwNGJcdTMwODkgMyBcdTY3OWFcdTMwOTJcdTkwNzhcdTMwNzNcdTY1NzRcdTY1NzBcdTMwOTJcdTRmNWNcdTMwOGJcdTMwNTNcdTMwNjhcdTMwOTJcdTgwMDNcdTMwNDhcdTMwOGJcdWZmMGUgMiwgMSwgMTMgXHUzMDkyXHUzMDUzXHUzMDZlXHU5ODA2XHUzMDZiXHU0ZTI2XHUzMDc5XHUzMDhiXHUzMDY4XHVmZjBjXHU2NTc0XHU2NTcwIDIxMTMgXHUzMDkyXHU0ZjVjXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDRjXHUzMDY3XHUzMDRkXHUzMDhiXHVmZjBlIFx1MzA3ZVx1MzA1Zlx1ZmYwYzIxLCAxLCAzIFx1MzA5Mlx1MzA1M1x1MzA2ZVx1OTgwNlx1MzA2Ylx1NGUyNlx1MzA3OVx1MzA2Nlx1MzA4Mlx1ZmYwY1x1NTQwY1x1MzA1OFx1NjU3NFx1NjU3MCAyMTEzIFx1MzA5Mlx1NGY1Y1x1MzA4Ylx1MzA1M1x1MzA2OFx1MzA0Y1x1MzA2N1x1MzA0ZFx1MzA4Ylx1ZmYwZSBcdTMwNTNcdTMwNmVcdTMwODhcdTMwNDZcdTMwNmJcdWZmMGNcdTc1NzBcdTMwNmFcdTMwOGJcdTMwYWJcdTMwZmNcdTMwYzlcdTMwNmVcdTdkNDRcdTMwN2ZcdTU0MDhcdTMwOGZcdTMwNWJcdTMwNGJcdTMwODlcdTU0MGNcdTMwNThcdTY1NzRcdTY1NzBcdTMwNGNcdTRmNWNcdTMwODlcdTMwOGNcdTMwOGJcdTMwNTNcdTMwNjhcdTMwODJcdTMwNDJcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+biBcdTY3OWFcdTMwNmVcdTMwYWJcdTMwZmNcdTMwYzlcdTMwNmJcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNWZcdTY1NzRcdTY1NzBcdTMwNGNcdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdTMwNWZcdTMwNjhcdTMwNGRcdWZmMGMgXHUzMDVkXHUzMDZlXHU0ZTJkXHUzMDRiXHUzMDg5IGsgXHU2NzlhXHUzMDkyXHU5MDc4XHUzMDczXHVmZjBjXHU2YTJhXHU0ZTAwXHU1MjE3XHUzMDZiXHU0ZTI2XHUzMDc5XHUzMDhiXHUzMDUzXHUzMDY4XHUzMDY3XHU0ZjVjXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDRjXHUzMDY3XHUzMDRkXHUzMDhiXHU2NTc0XHU2NTcwXHUzMDZlXHU1MDBiXHU2NTcwXHUzMDkyXHU2YzQyXHUzMDgxXHUzMDhiXHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGUwXHUzMDkyXHU0ZjVjXHU2MjEwXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdTUxNjVcdTUyOWJcdTMwNmYgMituIFx1ODg0Y1x1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4Ylx1ZmYwZSAxIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2Zlx1MzBhYlx1MzBmY1x1MzBjOVx1MzA2ZVx1Njc5YVx1NjU3MCBuIFx1ZmYwODQgXHUyMjY2IG4gXHUyMjY2IDEwXHVmZjA5XHUzMDRjXHVmZjBjIDIgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHUzMGFiXHUzMGZjXHUzMGM5XHUzMDkyXHU5MDc4XHUzMDc2XHU2NzlhXHU2NTcwIGsgXHVmZjA4MiBcdTIyNjYgayBcdTIyNjYgNFx1ZmYwOVx1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZSAyK2kgXHU4ODRjXHU3NmVlXHVmZjA4MSBcdTIyNjYgaSBcdTIyNjYgblx1ZmYwOVx1MzA2Ylx1MzA2ZiBpIFx1Njc5YVx1NzZlZVx1MzA2ZVx1MzBhYlx1MzBmY1x1MzBjOVx1MzA2Ylx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4YiAxIFx1NGVlNVx1NGUwYSA5OSBcdTRlZTVcdTRlMGJcdTMwNmVcdTY1NzRcdTY1NzBcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHU1MWZhXHU1MjliXHUzMDZmXHVmZjBjXHU4MmIxXHU1YjUwXHUzMDU1XHUzMDkzXHUzMDRjXHU0ZjVjXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDRjXHUzMDY3XHUzMDRkXHUzMDhiXHU2NTc0XHU2NTcwXHUzMDZlXHU1MDBiXHU2NTcwXHUzMDZlXHUzMDdmXHUzMDkyXHU1NDJiXHUzMDgwIDEgXHU4ODRjXHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1Yzc3Y1x1YmNmOFx1YzViNCJ9XQ==