2011 ACM ICPC Kanpur problem

This problem ARITHMANCY appeared in Kanpur regionals.
Can anyone tell me the logic behind this problem ?
What I am able to figure to is that I have to use sieve of Eratosthenes to generate primes and use that somehow…

Can anyone tell me how to figure out the n!^n! part ?? I am not able to conclude anything[mathematically] from this point…