Squished Status#2823
Some engineers got tired of dealing with the many different ways of encoding status messages, so they decided to invent their own system. In their scheme, an encoded status message consists of a sequence of integers, each representing a character of the message, separated by spaces. Each integer is between and , inclusive. Unfortunately, they decided to compress the encoded messages by removing all spaces!
Your task is to determine how many different original encoded status messages could produce a given compressed status message. Since this number may be very large, output your answer modulo (0xfaceb00c in hexadecimal).
For example, if the compressed message is , the original message could have been or . The lengths of the compressed messages are between and characters, inclusive.
The first line contains a single integer (1 \le N \le 25), the number of compressed status messages to analyze. Each of the next lines contains an integer (2 \le M \le 255), the largest character code in that database, followed by the compressed message. All items in the input are separated by whitespace. It is guaranteed that the length of each compressed message .
For each test case, numbered in order from to , output Case #i: followed by a single integer — the number of different encoded status messages that could correspond to the compressed sequence. If no valid message exists, output .
Example 1