Little Tanjima loves to play with numbers. Her favorite subject is math. Recently her tutor Zuaina taught her how to find f(n) = mn where f(n) = m1 × m2 × m3 × …….×mn. Little Tanjima finds it so interesting that she asked for her homework task (Since she is a nerd from her little age, she never misses to ask for homework task from her teacher). She is pretty good with counting so Zuaina planned to give her a hard task. Before giving her HW problems Zuaina introduced her how Modulus (%) works in computing. By definition, the modulo operation finds the remainder after division of one number by another. Zuaina also promised to treat her with a box of Ferrero Rocher if she can solve the homework. Tanjima loves Ferrero Rocher ❤
Now Tanjima’s homework task is to determine f(n)=mn where m = 15 always and 0 ≤ n ≤ 1018 and she has to write down the answer P she gets by P = f(y)%k where k = 102.
Little Tanjima couldn’t solve the problems that were given by Zuaina. So, she started crying out loud as she won’t be able to get Ferrero Rocher. Her Elder brother Jumar feels sad for her and tries to help her to complete her homework so that the next day she gets Ferrero Rocher and also he can take some from her as payment :p But Jumar fell into trouble because Tanjima was giving n values so fast that jumar couldn’t calculate all in his mind. So he asked you for help. Can you write a program that can find the answer P for any value of n as fast as possible?
Input
The input contains only one integer n (0 ≤ n ≤ 1018). The value for m is 15 for all the case.
Output
Print the value for P. Remember
P = f(y)%k where f(y) = 15n and k = 102
Sample
| Input | Output |
|---|---|
3 | 75 |
