URI Online Judge | 1626

The Incredible Chapecoense Pizza Contest

By Leandro Zatesko, UFFS BR Brazil

Timelimit: 3

The universities from the brazilian region known as Southern Border (Fronteira Sul, in Portuguese) have been joining ACM ICPC South America/Brazilian Subregional for many years, alternating the First Phase site especially between the cities of Erechim, in the state of Rio Grande do Sul, and Chapecó, in the state of Santa Catarina. Since last year, our site has been being the 2nd greatest of the country. In this year of 2014, 34 teams of 12 institutions have joined the contest at UNOCHAPECÓ, at Chapecó. The institutions involved in the organisation of the contest — particularly UNOCHAPECÓ, UNOESC and just created UFFS — believe that Programming contests are one of the main goals to strengthen Programming culture, promoting scientific and technological independence and inovation and greater relevance in the national scenario.

After 2014 First Phase Awards, students and professors from the above institutions went to a caster pizza house for two reasons: 1. to end the hunger; 2. to talk about the organisation of the Programming contest at the knowledge, culture and education fair of Chapecó, named ‘Feira de Conhecimento, Cultura e Educação’ (FACE), which would happen two weeks later. But one of the professors during the talk proposed: “Why don't we realise a contest right here, not a Programming contest, but a pizza one? Whoever eats less pizza pays a round of beer for all!”. Everybody agreed, and therefore happened the 1st Incredible Chapecoense Pizza Contest (ICPC). The loser however wanted first to avoid paying the beer. “I pay only if someone can tell me a perfect number which is also a factorial number”, he said. “6”, answered another student quickly.

Is there another perfect number which is also a factorial number? Of course not, but the loser, outraged after paying beer for all, decided to make a program to convince himself. Recall: a positive integer M is said to be perfect if it equals the sum of all its divisors different from M (e.g. 6 = 1 + 2 + 3 and 28 = 1 + 2 + 4 + 7 + 14), and is said to be a factorial if there is a natural number N such that N! = M.

Input

Each line of input consists of a single integer N (2 ≤ N ≤ 105). The input ends in end-of-file (EOF).

Output

For each integer N read from input, print a line containing two values: the sum of the divisors of N! different from N! and N! itself. As both values can be very large, print just the remainder they leave by 109 + 7.

Sample Input Sample Output

2
3
4
5

1 2
6 6
36 24
240 120