1968 - A Terra Desconhecida

  • ID: 1968
  • IdBecrowd: 1968
  • Tags: matematica
  • Nível: 7
  • Tempo Limite: 2 segundos
  • Memória: 200 MB
  • Categoria: Matemática
  • Autor: Leandro Zatesko

Descrição

No último dia 12 de outubro comemoramos no Brasil o Dia das Crianças. Quem dera nós adultos vivêssemos mais no mundo das crianças, pois o inverso não tem dado certo, não mesmo. Nós adultos dividimos o mundo em nações, e são as crianças que mais sofrem com as guerras. Nós adultos criamos um sistema de distribuição de riqueza, e são as crianças que mais sofrem com a fome. Mas há uma Terra Desconhecida, não muito distante daqueles que ainda conservam um pouco da sua imaginação, que pertence às crianças. Lá não há guerra, não há pobreza, não há fome. Lá as crianças brincam dia e noite.

Mas uma catástrofe está ocorrendo com a Terra Desconhecida. Uma catástrofe! Os carneiros que habitavam a Terra Desconhecida acabaram ficando velhos, ou doentes, ou engolidos por jiboias. Com isso, os baobás começaram a crescer e tomaram conta da Terra Desconhecida. Agora, os cidadãos precisam se mudar urgentemente. Para auxiliar na evacuação, todos os cidadãos foram numerados de A a B (é óbvio que essa ideia foi dos adultos — eles adoram essas coisas!). Para definir quem seriam os líderes dos grupos durante a evacuação, alguém sugeriu que os líderes deveriam ser todos aqueles que houvessem recebido um número primo (é óbvio que essa ideia foi de uma criança — crianças têm muita imaginação e adoram se deleitar com coisas que dispensam maiores explicações!). Mas logo outra ideia surgiu:

— Um número primo é um número que possui exatamente 2 divisores. E se os líderes fossem aqueles que receberam um número com exatamente N divisores?

Todas as crianças adoraram a ideia. Já os adultos ficaram um longo tempo debatendo sobre como o número N deveria ser escolhido. Quando finalmente o número N foi escolhido, cada cidadão que não fosse líder de um grupo deveria escolher o grupo que quisesse para nele entrar. Nenhuma outra restrição foi imposta aos grupos. Nada impedia, por exemplo, que um grupo consistisse apenas do seu líder. Note que, dependendo do valor de N , nem haveria grupo algum.

Sabendo dos valores de A , B e N , solte a criança dentro de você e tente descobrir o número total de possibilidades para a formação dos grupos. Se, por exemplo, A = 5, B = 8 e N = 4, situação em que os líderes são os cidadãos 6 e 8, há 4 possibilidades:

ambos os cidadãos 5 e 7 escolhem entrar para o grupo liderado pelo cidadão 6;

ambos os cidadãos 5 e 7 escolhem entrar para o grupo liderado pelo cidadão 8;

o cidadão 5 escolhe entrar para o grupo liderado pelo cidadão 6 e o cidadão 7 escolhe entrar para o grupo liderado pelo cidadão 8;

o cidadão 5 escolhe entrar para o grupo liderado pelo cidadão 8 e o cidadão 7 escolhe entrar para o grupo liderado pelo cidadão 6.

Entrada

A única linha da entrada consiste unicamente dos inteiros positivos A , B e N ( A ≤ B ; B , N ≤ 10 7 ).

Saída

Imprima uma linha contendo unicamente um valor que represente o número de possibilidades para a formação dos grupos. Como esse número pode ser muito grande, imprima apenas o resto que ele deixa quando dividido por 10 9 + 7.

Exemplos

Exemplo de Entrada

5 8 4

Exemplo de Saída

4
Back to top