compute $\sum_{k=0}^{(p-1)/2} \dfrac{(p-1)!}{(k!)^2(p-1-2k)!}\mod p$ 
Let $p$ be an odd prime. Compute $\sum_{k=0}^{(p-1)/2} \dfrac{(p-1)!}{(k!)^2(p-1-2k)!}\mod p.$

For an odd prime p, let $S(p) = \sum_{k=0}^{(p-1)/2} \dfrac{(p-1)!}{(k!)^2(p-1-2k)!}$.  Note that we may assume $p\equiv 1, 5\mod 6,$ since for $p=3$, we have $S(p) = \sum_{k=0}^1 \dfrac{2}{(k!)^2(2-2k)!} = 1+2 = 3\equiv 0\mod p.$ Computing a few more values, we get $S(5) = 4!(1 + 1/(1!^2\cdot 2!) + 1/(2!^2 \cdot 0!)) \equiv 2\mod 5, S(7) = 6! (1 + 1/(1!^2 \cdot 4!) + 1/(2!^2 \cdot 2!) + 1/(3!^2 \cdot 0!)) \equiv 6\mod 7.$  All congruences in this problem will be modulo p for simplicity. First consider the case where $p\equiv 1\mod 6$ and write $p= 6r + 5$ for some $r\ge 0$. Then $(p-1)/2 = 3r+2.$
We have $S(p) = \sum_{k=0}^{(p-1)/2} \dfrac{(p-1)(p-2)\cdots (p-2k)}{(k!)^2} \equiv \sum_{k=0}^{(p-1)/2} \dfrac{(2k)!(-1)^{2k}}{(k!)^2} = \sum_{k=0}^{(p-1)/2} \dfrac{(2k)!}{(k!)^2}$
But I'm not sure how to simplify this result. Would the Binomial Theorem be useful?
 A: $$\begin{aligned}
(2k)!&=(2k)(2k-2)\cdots2\cdot(2k-1)(2k-3)\cdots1\\
&=k!2^k(2k-1)(2k-3)\cdots1\\
&=k!(4k-2)(4k-6)\cdots2\\
&\equiv_pk!(4k-2-2p)(4k-6-2p)\cdots(2-2p)\\
&=k!(-4)^k(\frac{p-1}2-k+1)(\frac{p-1}2-k+2)\cdots \frac{p-1}2
\end{aligned}$$
The idea of the transformation above comes from this comment.
$$\begin{aligned}
&\sum_{k=0}^{(p-1)/2} \dfrac{(p-1)!}{(k!)^2(p-1-2k)!}\\
&\equiv_p\sum_{k=0}^{\frac{p-1}2} \dfrac{(2k)!}{(k!)^2}\\
&=\sum_{k=0}^{\frac{p-1}2}\frac{k!(-4)^k({\frac{p-1}2}-k+1)({\frac{p-1}2}-k+2)\cdots {\frac{p-1}2}}{(k!)^2}\\
&=\sum_{k=0}^{\frac{p-1}2}(-4)^k\frac{({\frac{p-1}2}-k+1)({\frac{p-1}2}-k+2)\cdots {\frac{p-1}2}}{k!}\\
&=\sum_{k=0}^{\frac{p-1}2}(-4)^k{{\frac{p-1}2}\choose k}\\
&=(1+(-4))^{\frac{p-1}2}\\
&=(-3)^{\frac{p-1}2}\\
&=(-1)^{\frac{p-1}2}3^{\frac{p-1}2}\\
&\equiv_p(-1)^{\frac{p-1}2}\left({\frac {3}{p}}\right)\\
&=(-1)^{\frac{p-1}2}\left({\frac {p}{3}}\right)(-1)^{\frac{3-1}2\frac{p-1}2}\\
&=(-1)^{p-1}\left({\frac {p}{3}}\right)\\
&=\left({\frac {p}{3}}\right)\\
&=\begin{cases}
  1 &\text{ if } p\equiv_31,\\
  0 &\text{ if } p=3,\\
  -1 &\text{ if }p\equiv_3-1\end{cases}
\end{aligned}$$
The place where $(1+(-4))^{\frac{p-1}2}$ appears uses the binomial theorem.
$(\frac{3}{p})$ and $(\frac{3}{p})$ are Legendre symbols.
The place where $(-1)^{\frac{3-1}2\frac{p-1}2}$ appears uses the law of quadratic reciprocity.
