Given ODD primes $p \neq q:$ and $$ \color{magenta}{p \equiv 3 \pmod 4} $$
Lemma: $$ (-p|q) = (q|p). $$
Lemma: If $$ a^2 + p \equiv 0 \pmod q, $$ THEN $$ (q|p) = 1. $$
Let $$ F_1 = 4 + p, $$
$$ F_2 = 4 F_1^2 + p, $$
$$ F_3 = 4 F_1^2 F_2^2 + p, $$
$$ F_4 = 4 F_1^2 F_2^2 F_3^2 + p, $$
$$ F_5 = 4 F_1^2 F_2^2 F_3^2 F_4^2 + p, $$
and so on.
These are all of the form $a^2 + p$ and are odd, so the only primes than can be factors are quadratic residues for $p.$ Next, all the $F_j$ are prime to $p$ itself. Finally, these are all coprime. So, however they factor, we get an infinite list of primes that are quadratic residues of $p.$
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Given ODD primes $p \neq q:$ and $$ \color{magenta}{p \equiv 1 \pmod 4} $$
Lemma: $$ (p|q) = (q|p). $$
Lemma: If $$ a^2 - p \equiv 0 \pmod q, $$ THEN $$ (q|p) = 1. $$
FIND an even square $$ W = 4^k = \left( 2^k \right)^2 $$ such that
$$ \color{magenta}{ W > p.} $$
Let $$ F_1 = W - p, $$
$$ F_2 = W F_1^2 - p, $$
$$ F_3 = W F_1^2 F_2^2 - p, $$
$$ F_4 = W F_1^2 F_2^2 F_3^2 - p, $$
$$ F_5 = W F_1^2 F_2^2 F_3^2 F_4^2 - p, $$
and so on. As $p \equiv 1 \pmod 4$ and $W \equiv 0 \pmod 4,$ we know $W - p \equiv 3 \pmod 4 $ and so $W-p \geq 3. $ So the $F_j$ are larger than $1$ and strictly increasing.
These are all of the form $a^2 - p$ and are odd, so the only primes than can be factors are quadratic residues for $p.$ Next, all the $F_j$ are prime to $p$ itself. Finally, these are all coprime. So, however they factor, we get an infinite list of primes that are quadratic residues of $p.$
Suppose there are $n$ and $k$ such that $$ (a_1!-1)(a_2!-1)...(a_n!-1)=k^2+16=k^2+4^2\quad (*).$$
Notice that $4$ can not divide the LHS, and consequently $\mathrm{gcd}(k,4)=1$. Then by step $4$ here, every factor of $k^2+4^2$ is a sum of two squares. That is, for all $i=1,\ldots,n$, there are integers $a$ and $b$ such that $$a_i!-1=a^2+b^2.$$
If $a_i\geq 4$, then $a_i!-1\equiv -1\pmod 4$, but $a^2+b^2\not\equiv -1 \pmod 4$. Hence we must have $a_i\leq 3$ for all $i=1,\ldots,n$.
It follows that the LHS in $(*)$ is either zero, which is impossible, or equal to $$(3!-1)^m=5^m$$
for some $0\leq m \leq n$.
Now let's solve $$ k^2+4^2=5^m.$$
- If $m$ is even, say $m=2c$, then $k^2+4^2=5^{2c}$ yields $2^4=4^2=(5^c-k)(5^c+k)$. Consequently $5^c-k=2^{u}$ and $5^c+k=2^v$ for some $u,v\geq 0$ with $u+v=4$. This is easy to solve, by just discussing cases.
- If $m$ is odd, say $m=2c+1$, then $k^2+4^2=5\cdot 5^{2c}$ yields $$k^2=((2\omega -1) 5^c-4)((2\omega -1) 5^c+4),$$
where $w=\frac{1+\sqrt{5}}{2}$.
The ring $\mathbb{Z}[\omega]$, which is the ring of integers of $\mathbb{Q}(\sqrt{5})$, is a UFD; see oeis.org/A003172. Moreover $(2\omega -1) 5^c-4$ and $(2\omega -1) 5^c+4$ are coprime (because if $p$ is irreducible and divides $(2\omega -1) 5^c-4$ and $(2\omega -1) 5^c+4$, then $p\bar{p}\mid 8$ and so $p\bar{p}=2\mid k^2$, which is impossible). Hence both factors are squares in $\mathbb{Z}[\omega]$, that is, $$(2\omega -1) 5^c-4=(e+\omega f)^2$$
for some $e,f\in \mathbb{Z}$. But using the fact that $\omega^2= 1+\omega$, we can see that the last equation has no solutions in $e,f\in \mathbb{Z}$.
Consequently all the solutions, if any (as I didn't do the computation), come from the case where $m$ is even.
Best Answer
We claim that every solution $(a_1,\dots,a_n)$ has $n-2$ variables equal to $2$ and the other two variables equal to $3$; the formula $N_n = \binom n2 = \frac{n(n-1)}2$ follows immediately from this claim. It's easy to check that these are indeed all solutions, since then the left-hand side equals $(2!-1)^{n-2}(3!-1)^2-16 = 1^{n-2}5^2-16=9=3^2$.
Suppose first that some $a_j\ge4$. Then $a_j!$ is divisible by $4$, so $a_j!-1\equiv3\pmod4$ and hence is divisible by some prime $p\equiv3\pmod4$. Modulo this prime we have $(a_1!-1)\cdots(a_n!-1)-16\equiv-16\pmod p$; but $-1$ is a quadratic nonresidue modulo $p$ since $p\equiv3\pmod 4$, and hence so is $-16=-(4^2)$. Therefore $(a_1!-1)\cdots(a_n!-1)-16$ is not a square modulo $p$ and hence cannot be a square.
The only remaining possibilities are that $(a_1,\dots,a_n)$ consists of $k$ copies of $3$ and $n-k$ copies of $2$. We easily work out then that $(a_1!-1)\cdots(a_n!-1)-16 = (2!-1)^{n-k}(3!-1)^k-16 = 5^k - 16$, which is not a square for $k=0,1$ (and is a square for $k=2$ as noted above). The other cases can be disposed of:
Remarks: