Некоторым инженерам надоело иметь дело с различными способами кодирования сообщений, поэтому они решили придумать свои собственные. В новой схеме закодированное сообщение состоит из последовательности целых чисел, представляющих символы сообщения, разделенных пробелами. Каждое целое число находится в границах от \textbf{1} до \textbf{M} включительно. К сожалению, было решено сжать закодированное сообщение, удалив все пробелы! Вам следует выяснить, сколько разных исходных сообщений могут соответствовать заданному закодированному сжатому сообщению. Поскольку это число может быть велико, ответ следует выводить по модулю \textbf{4207849484 }(\textbf{0xfaceb00c} в шестнадцатиричной системе счисления). Например, закодированное сообщение "\textbf{12}" могло быть изначально "\textbf{1 2}" или "\textbf{12}". Длина закодированного сжатого сообщения может изменяться от \textbf{1} до \textbf{1000} символов включительно. \InputFile Первая строка содержит количество закодированных сообщений \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{25}), которое следует проанализировать. Далее следуют \textbf{N} сообщений, каждое из которых задается целым числом \textbf{M} (\textbf{2} ≤ \textbf{M} ≤ \textbf{255}) - наибольшим кодом символа в базе кодирования, и самим сжатым сообщением. Известно, что \textbf{1} ≤ длина сжатого закодированного сообщения ≤ \textbf{1000}. \OutputFile Для каждого теста, пронумерованного числами от \textbf{1} до \textbf{N}, вывести строку "\textbf{Case #i:} ", за которой следует количество различных сообщений, задающих в сжатом виде входную последовательность. Если таких сообщений не существует, то вывести \textbf{0}.