String Hashing

String hashing turns an arbitrary string into a single number. For a string $S$ of length $N$, define its hash as

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

where $S[i]$ is the ASCII code of the $i$-th character and $31^k$ means 31 multiplied by itself $k$ times. The computation uses big integer arithmetic, so it never overflows.

Here are a few strings and their hashes.

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

Different strings sometimes share a hash, as the second and third strings do.

A string is valid if the ASCII code of every one of its characters is between 32 and 126, inclusive.

Count the valid strings whose hash equals the hash of a given string.

The input has several lines. Each line describes one string as a sequence of space separated integers in the format

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

$N$ is the length of the string ($1 \le N \le 1000$) and $S[i]$ is the ASCII code of the $i$-th character ($32 \le S[i] \le 126$).

A line with $N = 0$ marks the end of the input and is not processed.

For each string, print on one line the number of valid strings whose hash equals its hash, modulo $1\,000\,000\,007$. The count includes the given string itself.

The hash of "ab" is 3105. Two other valid strings have that hash, "bC" (ASCII 98 67) and "c$" (ASCII 99 36), so the answer is 3 including "ab" itself. The string with ASCII codes 100 5 also hashes to 3105, but it is not valid because 5 is below 32.

The hash of "Hi!" is 72480, and 12 valid strings have that hash.

The hash of the string made of three spaces is 31776, and no other valid string has that hash.