How to check if $5$ is a square $\mod 701$ without a calculator

Question

The Legendre symbol tells us to calculate $5^{350} \mod 701$, but this question was on an exam where no calculators are allowed, so I wasn't able to do this question. How can you find if $5$ is a square $\mod 701$ without a calculator if $701$ is prime? What if it's not a prime number?

Answer 1

Use the law of quadratic reciprocity.

Answer 2

Is there anyway to solve this using Fermat's little theorem? a^(p-1) ≡ 1 mod p.

5^700 ≡ 1 mod 701

(5^350)^2 ≡ 1 mod 701

But I'm not sure if this tells us anything about 5^350 mod 701