조이는 길이 막히는 차에서 너무 지루한 나머지 숫자놀이를 하기로 했다. 먼저 마음속으로 숫자 K를 정한다. 그 다음, K자리이면서 모든 숫자가 0 이상 K 이하인 표지판을 하나 고른다. 이제 이 숫자를 다른 숫자로 바꾸는데, 1번째 자리가 1의 개수고, 2번째 자리가 2의 개수고, ..., K번째 자리가 K의 개수인 K자리 숫자를 만든다.

조이는 놀이를 하다가 하나 궁금한 점이 생겼다. 조이가 표지판을 봤을 때, 그 표지판의 숫자를 만들 수 있는 표지판이 몇 가지나 있는지 궁금했다. 이 표지판은 K자리이고, 모든 자리수가 0 이상 K 이하여야 한다는 점에 유의하자. 하지만 조이에게는 너무 어려운 문제였기 때문에, 여러분에게 도움을 청했다.

조이가 0414라는 표지판을 봤다고 해보자. 이 표지판은 1이 1개, 2가 0개, 3이 0개, 4가 2개이기 때문에 1002로 바뀐다. 이 숫자를 여러번 바꾸면 1100, 2000, 0100, 1000 순서로 바뀌게 된다. 1000은 항상 자기 자신으로 바뀐다. 즉, 1000을 만들 수 있는 표지판에는 1000, 0100, 2000, 1100, 1002, 0414 등이 있다.

표지판의 번호가 주어졌을 때, 표지판의 번호를 만들 수 있는 숫자의 개수를 구해주자.

#3168 upload 82 done 4 how_to_reg 4

표지판 timer 7s memory 256MB

#3168

표지판 7s 256MB