# SPOJ CRYPTO1

## Summary

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

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

## Explanation

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

${\displaystyle x^{2}\equiv q\;(mod\;n).}$

When ${\displaystyle q}$ and ${\displaystyle n}$ are mutually prime, it is solvable if ${\displaystyle a^{p-1}\equiv +1\;(mod\;p)}$. It will always be ${\displaystyle 1}$ or ${\displaystyle -1}$, because of Fermat's Little Theorem. When p is of the form ${\displaystyle 4k+3}$ (like 4000000007), the solutions will be ${\displaystyle x=a^{k+1}\;(mod\;p)}$ and ${\displaystyle 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