Optimizing NOI Extraction After Insertion

In this problem, you are given a sequence of characters, each being one of N, O, or I. Initially, these cores are arranged in a row. During the "refinement" process, small A takes out three cores in order: first an N, then an O, and finally an I (the three letters must appear in this order in the sequence, however, they need not be consecutive).

However, A is not satisfied with the number of ways he can take out the triple. Therefore, he can obtain one extra core – he can choose arbitrarily one among N, O, or I – and insert it at any position in the sequence (including at the beginning or end). After that, he again takes out an N, then an O, and then an I from the new sequence.

Your task is to choose the type of the extra core and its insertion position optimally (if needed) so that the number of ways to extract the triple N, O, I (in that strict order) is maximized. Output this maximum possible number of extraction ways.

The number of extraction ways is defined as follows. Given a sequence T (of length L), a valid extraction is a triple of indices i < j < k such that T[i] = N, T[j] = O, and T[k] = I. Let f(T) be the total number of such triples.

The original sequence is s and its extraction count is f(s). If you insert an extra core at position p (0-indexed in the new sequence, meaning that the extra core is inserted between s[0..p-1] and s[p..end]) with one of the three types, then the new extraction count f(s') can be described in terms of an additional contribution over f(s). More precisely, if you let:

• For an insertion of N: additional = number of Os in s[p...n-1].
• For an insertion of O: additional = (number of Ns in s[0...p-1]) * (number of Is in s[p...n-1]).
• For an insertion of I: additional = number of Os in s[0...p-1].

Your goal is to compute the maximum value of f(s) + additional over all valid insertion positions p (from 0 to n) and for all possible choices of the extra core. You are given the original sequence s as input.

Note: The inserted extra core might affect some extraction counts by becoming part of the count for the prefix or suffix; however, only the above contributions are added to f(s) due to the insertion.

inputFormat

The input consists of a single line containing a non-empty string s composed only of the characters N, O, and I.

outputFormat

Output a single integer representing the maximum possible number of extraction ways in the new sequence after inserting one extra core optimally.

sample

NOI

2