29143번 - Шифровка 다국어

문제

Мориарти умер, но у него осталось множество последователей. И вот вчера в город с важным посланием прибыл один из них. Подкараулив его, Ватсон и Холмс поймали преступника, нашли у него в кармане письмо с посланием и стали допрашивать.

Допросив его, они узнали следующую информацию: в письме содержится зашифрованное описание коварного плана, который Мориарти не успел осуществить при жизни. Всю информацию злой гений предпочитал хранить в двоичном коде --- в виде строки, состоящей из нулей и единиц. Для шифрования сообщения, описывающего его коварный план, Мориарти использовал следующий алгоритм: он разбил строку, хранящуюся в двоичном коде, на максимальные по размеру группы подряд идущих одинаковых символов, а затем каждую группу заменил на соответствующий символ и количество его вхождений в данную группу. К примеру, группу 111 он заменит на 13, а группу 0000000000 на 010. Тогда строку 11100 Мориарти заменит на 1302, а строку 00000000001 на 01011.

Также оказалось, что после применения этого алгоритма шифрования к строке, описывающей коварный план, получилась строка, которая также является строкой, записанной в двоичном коде. Эту строку и послал в письме профессор.

Больше ничего узнать про это послание не удалось. Теперь Шерлок задался вопросом: как узнать, что именно было зашифровано? Однозначно вряд ли получится узнать. Поэтому он хочет узнать хотя бы количество возможных сообщений, которые после шифрования совпали бы с сообщением, которое они с Ватсоном перехватили. Это количество может быть довольно большим, поэтому Холмс просит Вас только найти его остаток от деления на 1ドル,000円,000円,007円$.

입력

В первой строке входного файла дано одно число $n$ --- длина сообщения, которое перехватили Холмс и Ватсон (1ドル \le n \le 100,000円$).

Во второй строке входного файла дано это сообщение --- строка длиной $n,ドル состоящая из символов 0 и 1.

출력

В единственной строке выходного файла выведите количество возможных исходных сообщений по модулю 1ドル,000円,000円,007円$.

제한

힌트