ATM 비밀번호 훔쳐보기

개비(Gabby)가 ATM 키패드에서 네 자리 비밀번호(PIN)를 입력하는 동안, 빌리(Billy)가 어깨너머로 이를 훔쳐보며 비밀번호를 알아내려 한다. 이 키패드에서는 키를 누른 채로 오래 유지하면 같은 키가 여러 번 입력될 수 있다. 입력된 모든 숫자는 화면에 *로만 표시되므로, 빌리는 실제 숫자를 읽을 수 없다. 그는 개비가 어떤 키를 어떤 순서로 눌렀는지만 볼 수 있을 뿐, 각 키가 실제로 몇 번 입력되었는지는 알 수 없다.

비밀번호는 정확히 네 자리 숫자(0–9) 문자열이다. 키패드에는 숫자 키 10개와, 가장 최근에 입력된 숫자를 지우는 백스페이스 키 1개가 있다. 다른 키와 마찬가지로 백스페이스도 누른 채로 유지하면 한 번에 여러 숫자가 지워질 수 있다. 빌리는 (백스페이스를 포함하여) 각 키 입력을 올바른 순서로 보지만, 각 키가 몇 번 입력되었는지는 결코 알지 못한다. 비밀번호는 정확히 네 자리이지만, ATM은 몇 번의 키 입력이든 받아들이므로 개비는 네 개보다 많은 키를 누를 수도 있고(그중 일부 숫자는 나중에 백스페이스로 지워진다), 키를 길게 눌러 여러 번 입력되게 함으로써 네 개보다 적은 키를 누를 수도 있다.

예를 들어 빌리가 개비의 입력을 1, 3, 5, 7 순서로 보았다면, 가능한 비밀번호는 1357 하나뿐이다. 그러나 관찰된 입력이 1, 3, 5 (이 순서)라면 비밀번호는 1135, 1335, 1355 중 하나일 수 있다.

빌리가 관찰한 키 순서가 주어질 때, 이와 모순되지 않는 서로 다른 비밀번호의 개수를 세어라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 번째 줄에는 개비가 누른 키의 개수를 나타내는 정수 $n$ ($0 < n < 10$)이 하나 주어진다. 다음 줄에는 공백으로 구분된 $n$개의 정수가 주어지며, 각 값은 한 자리 숫자(0–9)이거나 백스페이스 키를 뜻하는 99이다. 이들은 개비가 누른 키를 순서대로 나열한 것이다. 각 테스트 케이스에서 키 99는 최대 한 번만 나타나며, 다른 키는 여러 번 나타날 수 있다. 입력은 0 하나만 있는 줄로 끝난다.

각 테스트 케이스마다, 관찰된 키 순서와 모순되지 않는 서로 다른 네 자리 비밀번호의 개수를 한 줄에 출력한다. 모순되지 않는 비밀번호가 하나도 없으면 0을 출력한다.