The Chinese (Lunar) New Year festivities are in full swing along the West Kowloon Waterfront Promenade. During the Lantern Festival, the day marking the end of the Lunar New Year, a popular activity at night is known as "caai dang mai" (猜燈謎), i.e. "guessing lantern riddles", where children go out at night carrying paper lanterns and solve riddles on the lanterns, often related to guessing meanings of phrases. These riddles, written on slips of paper and attached to the lanterns, offer a fun challenge for young and old alike.

Lantern riddles (© Epoch Group Limited)

This year, a particularly interesting lantern riddle has captured everyone's attention. Instead of traditional riddles displayed on one lantern, there is a row of $$$N$$$ consecutive lanterns labelled 1, 2, ..., $$$N$$$, where the $$$i$$$-th lantern ($$$1 \leq i \leq N$$$) displays a string of lowercase characters $$$S_i$$$. It is guaranteed that all $$$S_i$$$ are distinct. The challenge is to find combinations of lanterns that satisfy a special string triangle inequality.

We say that three strings $$$X$$$, $$$Y$$$, $$$Z$$$ satisfy the string triangle inequality if and only if for every permutation $$$[X', Y', Z']$$$ of $$$[X, Y, Z]$$$, the following condition is satisfied: $$$X' + Y' \gt Z'$$$. In other words, all of the following must be satisfied:

• $$$X + Y \gt Z$$$
• $$$X + Z \gt Y$$$
• $$$Y + X \gt Z$$$
• $$$Y + Z \gt X$$$
• $$$Z + X \gt Y$$$
• $$$Z + Y \gt X$$$

Here, + denotes the string concatenation operator, while > denotes the "lexicographically larger than" comparison operator (the same way + and > operate on strings in C++).

The lantern riddle is: count the number of tuples $$$(i, j, k)$$$ where $$$1 \leq i \lt j \lt k \leq N$$$ and the strings $$$S_i, S_j, S_k$$$ satisfy the string triangle inequality.