The Curse of the Black Pearl

The Black Pearl is known to exist. For a long time the famous Captain Jack Sparrow commanded it. The ship and its captain have been through fire, water, and worse. Scholars have established that the Black Pearl is the fastest ship in the world, faster than the Razyashchiy and the Flying Dutchman, which is said to sail faster than the wind.

After the treasury on Isla de Muerte was robbed, a curse fell on the crew of the Black Pearl and on the ship itself. The sails tore, and a creepy fog began to surround the vessel. The curse was too hard to lift, so nobody tried.

In the hold, on the most rotten board of the farthest wall, a riddle is written. It is the key to lifting the curse. The board is very old, and some letters have worn away. According to legend, the riddle had no spaces, so it looked like a single word. The riddle cannot be restored, so the curse cannot be lifted. It can, however, be softened.

According to the Sage, softening the curse requires throwing a large bag of gold overboard. For every substring of the riddle word that could have all equal letters under some filling of the gaps, one coin goes into the bag.

Given the riddle, determine how many coins must be thrown overboard to soften the curse.

The input file contains one string of length at most $10^6$. The string consists of lowercase Latin letters and question marks, where a question mark marks an erased letter (a gap).

Print one integer, the answer to the problem.

Exactly six substrings of the riddle in the first sample meet the conditions:

• Four single-character substrings: 'a', 'b', 'c', and '?' filled with any character.
• The substring 'b?' when the gap is filled with 'b'.
• The substring '?c' when the gap is filled with 'c'.