Order finding (exact)

Suppose $N\ge 2$, $x$ is an integer with $\gcd(x,N)=1$, $r$ is the least positive integer satisfying $x^r\equiv 1\pmod N$, and $q=2^t$ is a multiple of $r$. Given access to an oracle $U_x$ such that $U_x\ket{a,y}=\ket{a,y\oplus x^a\bmod N}$, there exists a quantum algorithm that outputs an index $j=s(q/r)$ for some $s\in\{0,\ldots,r-1\}$, using one query to $U_x$ and $\mathcal{O}(t^2)$ elementary gates.