레고 시퀀스 timer 2초 memory 1024MB

크기가 같은 N개의 큐브가 있으며, i 번째 큐브는 i 색상이다.

정올이는 큐브를 꽂을 수 있는 K개의 칸에 한 줄 모양으로 레고 베이스에 벽을 세우려고 한다.

다음과 같은 방법으로 큐브를 배치하려고 한다:

• 먼저, 색상 1의 큐브를 베이스의 임의의 지점에 놓는다.

• 색상 2부터 색상 N까지의 각 큐브에 대해 이전에 배치된 큐브와 인접한 지점에 큐브를 배치한다. 그 자리가 비어 있지 않으면 새 큐브를 이미 해당 자리에 있던 다른 큐브 위에 놓게 된다.

벽을 만들게 되면, i번째 위치에 놓인 큐브 중 맨 위의 큐브의 색상(색상이 없으면 0)이 적힌 길이 K의 레고 시퀀스가 생성된다.

값이 모두 동일해도 순서가 다른 두 레고 시퀀스는 서로 다른 것으로 간주된다. 총 몇 개의 서로 다른 레고 시퀀스가 생성되는 것이 가능한지 알아보자.