CF744E Hongcow Masters the Cyclic Shift

Hongcow's teacher heard that Hongcow had learned about the cyclic shift, and decided to set the following problem for him. You are given a list of $ n $ strings $ s_{1},s_{2},...,s_{n} $ contained in the list $ A $ . A list $ X $ of strings is called stable if the following condition holds. First, a message is defined as a concatenation of some elements of the list $ X $ . You can use an arbitrary element as many times as you want, and you may concatenate these elements in any arbitrary order. Let $ S_{X} $ denote the set of of all messages you can construct from the list. Of course, this set has infinite size if your list is nonempty. Call a single message good if the following conditions hold: - Suppose the message is the concatenation of $ k $ strings $ w_{1},w_{2},...,w_{k} $ , where each $ w_{i} $ is an element of $ X $ . - Consider the $ |w_{1}|+|w_{2}|+...+|w_{k}| $ cyclic shifts of the string. Let $ m $ be the number of these cyclic shifts of the string that are elements of $ S_{X} $ . - A message is good if and only if $ m $ is exactly equal to $ k $ . The list $ X $ is called stable if and only if every element of $ S_{X} $ is good. Let $ f(L) $ be $ 1 $ if $ L $ is a stable list, and $ 0 $ otherwise. Find the sum of $ f(L) $ where $ L $ is a nonempty contiguous sublist of $ A $ (there are  contiguous sublists in total).

The first line of input will contain a single integer $ n $ ( $ 1

Print a single integer, the number of nonempty contiguous sublists that are stable.

For the first sample, there are $ 10 $ sublists to consider. Sublists \["a", "ab", "b"\], \["ab", "b", "bba"\], and \["a", "ab", "b", "bba"\] are not stable. The other seven sublists are stable. For example, $ X $ = \["a", "ab", "b"\] is not stable, since the message "ab" + "ab" = "abab" has four cyclic shifts \["abab", "baba", "abab", "baba"\], which are all elements of $ S_{X} $ .