일방통행로를 따라 n개의 주차장들이 있다. 1부터 n까지 번호가 매겨진 n대의 차들이 한 대씩 이 길에 들어선다. 각 운전자 i는 그가 선호하는 주차장 p_i로  ㅣ향하는데,주차장이 비어있으면 그곳에 주차한다. 그렇지 않으면 비어 있는 다음 주차장으로 가서 그 곳에 주차한다. 이 후의 모든  주차장들이 이미  주차가  되어있으면,그는 그냥  가버린다. 모든 운전자들이 주차할 수 있는 순열 p는 몇가지인가?


답은 (n+1)^(n-1)이라는데ㅠㅠ  잘몰것네요
풀이방법이나  무슨  아이디어로  푸는지  알 .수 ㅇㅣㅆ을까요?