Notice that we don't need the whole words to solve the problem, only the first and last letters are important. Therefore, it is sufficient to memorize, for each pair of letters, the number of words that begin and end with the respective letters.

Now we can select all possible combinations of letters in the corners of the square (~26^4~ possibilities). For each combination, we simply add the number of possible squares with the respective corners.

On each edge, we can place any word starting and ending with the appropriate letters. This word selection would always be independent if we could use the same word multiple times in the same square. If the number of possible words on the appropriate edges is denoted by ~A~, ~B~, ~C~, and ~D~, the solution would be ~A \times B \times C \times D~ (ignoring the fact that we cannot select the same word multiple times).

However, if there are two edges requiring the same pair of beginning and ending letters, for example if the first two edges satisfy that constraint, the solution is ~A \times (A-1) \times C \times D~. It follows from the fact that we cannot choose from all ~A~ words for the second edge since we have already used one word up for the first edge.

By generalizing this result, we find that if ~K~ edges require the same pair of beginning and ending letters, and we have ~A~ such words, we can select the ~K~ edges in ~A \times (A-1) \times \dots \times (A-K+1)~ ways.

The complexity of the solution, not counting input, is ~\mathcal O(26^4)~.