# SPOJ CRYPTO1

## Summary

Given the result of applying a simple cryptographic function $f(n)$ , where $n$ is the number of seconds from midnight 1970.01.01 GMT to a certain date, we need to find the original date.

$f(n)=n^{2}\;mod\;4000000007$ ## Explanation

An integer $q$ is called a quadratic residue modulo $n$ if it is congruent to a perfect square (mod $n$ ); i.e. if there exists an integer x such that:

$x^{2}\equiv q\;(mod\;n).$ When $q$ and $n$ are mutually prime, it is solvable if $a^{p-1}\equiv +1\;(mod\;p)$ . It will always be $1$ or $-1$ , because of Fermat's Little Theorem. When p is of the form $4k+3$ (like 4000000007), the solutions will be $x=a^{k+1}\;(mod\;p)$ and $x=-a^{k+1}\;(mod\;p)$ . Only one of these will fit in the given range.

## Gotchas

• If you are using your programming language's date feature, make sure to take care of time-zones.

## Implementation

You can use the string "%a %b %d %T %Y" for the "strftime" function.

## Input

1749870067


## Output

Sun Jun 13 16:20:39 2004