$N$-факториалы растут очень быстро. Так, $5$-факториал это $1^1 \cdot 2^2 \cdot 3^3 \cdot 4^4 \cdot 5^5 = 86400000$, а $6$-факториал превышает $10^{12}$. Так как сумма, заданная в задаче, ограничена числом $10^9$, то ее слагаемыми могут быть только $N$-факториалы для $N \le 5$. Предподсчитаем все их значения.

Затем, также предподсчитаем все возможные суммы, которые могут получиться при сложении двух $N$-факториалов, за $O(N^2)$, и сохраним их в массиве.

Далее, получая чиcло на вход, нам остается лишь проверять, присутствует ли оно в нашем массиве. Это можно сделать при помощи бинарного или простого линейного поиска.