URI Online Judge | 1234

O Cálice de Fogo

Por Leandro Zatesko, UFFS BR Brazil

Timelimit: 1

Uma das provas do Torneio Tribruxo de 2015 será uma partida de futebol, e a Chapecoense tem treinado duro para enfrentar os jogadores de Hogwarts. A Associação Chapecoense de Futebol (ACF, ou simplesmente Chapecoense) é o time de futebol da cidade de Chapecó. Fundado em 1973, o time hoje joga entre os melhores times do Brasil, e não são uns adolescentes esquisitos de chapéu e vassoura que vão amedrontar nossos desbravadores guerreiros, mesmo que todos nós tenhamos ficado espantados quando o Cálice de Fogo escolheu os trouxas dos nossos jogadores para participarem do Torneio Tribruxo. Como já mencionamos, a história do time começa 1973 quando…

Interrompemos este texto para a transmissão de um comunicado urgente do Ministro da Magia.

Boa tarde, senhores e senhoras trouxas! Maldito o dia em que Dolores Umbridge saiu da prisão. Agora, vive a me atazanar com esses problemas de Matemática. E ela sabe que eu não sou bom nessas coisas. Enfim, vocês podem fazer um programa para me ajudar? O problema é o seguinte: ela me diz um número inteiro N e pede que eu lhe diga quantos divisores N tem e guarde esse N na minha cabeça. Até aí tudo bem. Não sou tão burro e não preciso de ajuda nesta parte. Mas daí ela fica me dizendo alguns números primos e, para cada primo p que ela diz, eu devo multiplicar p por N, atualizando o valor de N na minha cabeça, e, como se não bastasse, preciso ainda lhe dizer quantos divisores tem esse novo N que são compostos apenas por fatores primos menores que p. Por exemplo, se eu tenho guardado na minha cabeça N = 630 e ela diz p = 5, eu tenho que atualizar N para 3150 e dizer 6, pois os únicos divisores de 3150 compostos apenas por fatores primos menores que 5 são: 1, 2, 3, 6, 9 e 18. Mas o número N cresce muito rápido, e eu não quero perder o jogo para ela. Por favor, façam alguma coisa!

Entrada

A entrada é composta por no mínimo 2 e no máximo 105 linhas. A primeira linha consiste unicamente do inteiro N (2 ≤ N ≤ 1012). Cada uma das linhas seguintes consiste unicamente de um número primo p (2 ≤ p ≤ 107). Os inteiros são fornecidos na entrada na ordem em que são proferidos por Dolores Umbridge. A entrada termina em fim de arquivo.

Saída

Para cada primo p proferido por Dolores Umbridge, imprima uma linha consistindo unicamente da resposta que o Ministro da Magia deveria lhe dar. Como a resposta pode ser um número muito grande, imprima apenas o resto que a resposta deixa quando dividida por 109 + 7.

Exemplos de Entrada Exemplos de Saída

630
5
7
2
3
11

6
18
1
3
108

2
3
5
7
11

2
4
8
16

2
2
2
2
3

1
1
1
5