32287번 - 진수 정렬 (Hard)

문제

한별이는 길이 $N$의 $M$진수를 모두 모은 뒤 특별한 방식으로 정렬하려 한다.

정렬 기준은 다음과 같다.

• $M$진수 내 $M-1$인 자릿수의 개수로 오름차순 정렬한다.
• $M-1$의 개수가 같다면 $M-2$인 자릿수의 개수로 오름차순 정렬한다.
• ...
• 2ドル$의 개수가 같다면 1ドル$인 자릿수의 개수로 오름차순 정렬한다.
• $M$진수 내 모든 숫자의 개수가 같다면 $M$진수를 뒤집었을 때의 오름차순으로 정렬한다.

예를 들어, $N$이 2이고 $M$이 3일 때 $M$진수는 다음 순서로 정렬된다.

• 00
• 10
• 01
• 11
• 20
• 02
• 21
• 12
• 22

어느날 친구 선린이가 찾아와 길이가 $N$인 $M$진수 하나를 주며 몇 번째 위치에 있는지 알려달라고 했다. 하지만 한별이는 다른 일이 많아 아직 $M$진수들을 정렬하지 못했다. 한별이를 도와주자!

입력

첫째 줄에 $N$과 $M$이 공백을 사이에 두고 주어진다.

둘째 줄에 길이 $N$의 $M$진수 $S$가 주어진다.

$M$진수는 0으로 시작할 수 있다.

출력

주어진 $M$진수와 길이가 같은 모든 $M$진수를 정렬하였을 때, 주어진 $M$진수는 몇 번째 위치에 있는지 출력한다.

위치는 0번부터 시작한다.

제한

• 1ドル\le N\le 10$
• 2ドル\le M\le 10$

힌트