Count Good Prefixes

You are given an integer $n$ and a string $s$ consisting only of characters 'a' and 'b'. Consider a string $t = \underbrace{s + s + \dots + s}_{n\text{ times}}$, i.e. the string obtained by concatenating $n$ copies of $s$. Find the number of non-empty prefixes of $t$ in which the number of occurrences of 'a' is strictly greater than the number of occurrences of 'b'. ### Input - The first line of