문자열 해싱

문자열 해싱은 임의의 문자열을 하나의 수로 바꾸는 방법이다. 길이가 $N$인 문자열 $S$의 해시를 다음과 같이 정의한다.

$S[0] \times 31^{N-1} + S[1] \times 31^{N-2} + \cdots + S[N-2] \times 31 + S[N-1]$

$S[i]$는 $i$번째 문자의 ASCII 코드이고, $31^k$는 31을 $k$번 곱한 값이다. 계산은 큰 정수로 하므로 자리 넘침은 일어나지 않는다.

문자열 몇 개와 그 해시를 예로 들면 다음과 같다.

1. "ab" ($N = 2$, ASCII 코드 97 98), 해시 $= 97 \times 31 + 98 = 3105$
2. "Hi!" ($N = 3$, ASCII 코드 72 105 33), 해시 $= 72 \times 31^2 + 105 \times 31 + 33 = 72480$
3. "IJ!" ($N = 3$, ASCII 코드 73 74 33), 해시 $= 73 \times 31^2 + 74 \times 31 + 33 = 72480$

두 번째와 세 번째처럼 서로 다른 문자열의 해시가 같을 때도 있다.

모든 문자의 ASCII 코드가 32 이상 126 이하인 문자열을 올바른 문자열이라고 한다.

주어진 문자열과 해시가 같은 올바른 문자열이 몇 개인지 구한다.

입력은 여러 줄로 이루어진다. 각 줄은 공백으로 구분된 정수 나열로 문자열 하나를 나타내며, 형식은 다음과 같다.

$N\;S[0]\;S[1]\;\cdots\;S[N-1]$

$N$은 문자열의 길이이고 ($1 \le N \le 1000$), $S[i]$는 $i$번째 문자의 ASCII 코드다 ($32 \le S[i] \le 126$).

$N = 0$인 줄은 입력의 끝을 뜻하며 처리하지 않는다.

문자열마다 해시가 같은 올바른 문자열의 개수를 $1\,000\,000\,007$로 나눈 나머지를 한 줄에 출력한다. 개수에는 입력으로 주어진 문자열 자신도 포함한다.

"ab"의 해시는 3105이다. 해시가 3105인 올바른 문자열은 "bC"(ASCII 98 67)와 "c$"(ASCII 99 36) 두 개가 더 있으므로 자신을 포함해 모두 3개다. ASCII 코드가 100 5인 문자열도 해시가 3105지만 5가 32보다 작아서 올바른 문자열이 아니다.

"Hi!"의 해시는 72480이고, 해시가 72480인 올바른 문자열은 12개다.

공백 세 개로 이루어진 문자열의 해시는 31776이고, 해시가 31776인 올바른 문자열은 자신뿐이다.