Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TRADUTO2 - Tradutor alienígena

 

É de conhecimento público e notório que já fomos visitados por alienígenas diversas vezes. A grande dificuldade que temos, porém, é a comunicação com eles, por causa de grandes diferenças entre as línguas. Além disso, assim como nós, eles também têm várias línguas diferentes.

Com o intuito de auxiliar no processo de tradução, foi criado um método de mapeamento dos símbolos do alfabeto de cada língua alienígena, atribuindo um número inteiro para cada símbolo. Sendo assim, para um alfabeto alienígena com N elementos, atribui-se números de 1 a N a cada um.

O problema é que o encarregado de transcrever os textos alienígenas para números não foi muito cuidadoso e usou o mesmo espaçamento entre dígitos e números. Assim, por exemplo, digamos que para um alfabeto com 32 símbolos, uma sequência que deveria ser "31 20 4 19" virou "3120419". Como se pode notar, há diferentes maneiras válidas de interpretar essa sequência além da original, como por exemplo "3 1 20 4 19" e "31 20 4 1 9". Repare que a transcrição nunca usa zeros à esquerda de um número e, portanto, a sequência "3 12 04 19" é inválida, assim como "31 20 41 9" por conter um número (41) que não corresponde a um símbolo.

Tarefa

Dados a quantidade de símbolos do alfabeto e uma sequência transcrita, determine quantas sequências válidas podem ser formadas

Entrada

A entrada é composta por duas linhas. A primeira contém um número inteiro N (1 < N < 10100) que indica a quantidade de símbolos do alfabeto. A segunda linha contém uma cadeia de dígitos de tamanho mínimo 1 e tamanho máximo 100.000 que corresponde a sequência transcrita. .

Saída

Seu programa deve imprimir uma linha com o resto da divisão da quantidade de sequências válidas por 1.000.000.007.

Exemplo

Entrada
32
3120419 Saída 4 Entrada 32
4021333251231253 Saída 0 Entrada 500
12345 Saída 13

Adicionado por:Wanderley Guimarăes
Data:2011-04-28
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:OBI 2010 - fase 2 nível 2

hide comments
2014-01-17 22:55:04 Tiago Nápoli
Tive uns probleminhas com long (q n precisava usar e sei lá o q deu q tava dando resposta errada) mas o algoritmo é de boa
2014-01-17 22:54:23 Tiago Nápoli
Cara, n é tăo difícil assim , n coloca medo n kkkkkkk
2012-05-02 22:55:19 Glauco Buarque
cara isso ae parece dificil, mas é mais!

Last edit: 2012-05-02 22:56:04
2011-06-12 04:36:32 Edgar Lavor
Dica: cuidado ao trabalhar com a classe string do C++. Nesse problema vocę năo pode ter uma constante muito alta na complexidade, entăo usar string.size() e o próprio operador + da classe string pode te dar um TLE.

Last edit: 2011-06-12 04:40:17
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.