elementary number theory - Product of first values of totient function

Let $~p~$ be prime and $~n~$ some positive integer below $~10^9$. Is there an efficient way to compute product $~ \phi(1) \cdots \phi(n) \mod p~$? It is known that $~p > \sqrt{n}~$ (i don't know if this somehow can help).
I know how to compute values $~\phi(1), \cdots, \phi(n)~$ using sieve but memory limitations are too strict to keep them all. Isn't there more efficient approach when we need to deal with such product? May be there is some nice formula for it?

Thanks in advance for any ideas.

P.P.S.
The original problem is
http://www.e-olymp.com/en/problems/3243