Magic Postfix Substrings

Nitori is learning postfix expressions. She has an incomplete postfix expression \(E\) of length \(n\). Being a Youkai, she wants to find its magical property.

The expression contains the Bitwise Or operator (denoted as \(|\)), the Bitwise And operator (denoted as \(\&\)), and the numbers \(0\) and \(1\). Some operators are missing and are represented by \(?\). It is guaranteed that after replacing each \(?\) with either \(\&\) or \(|\), \(E\) becomes a valid postfix expression.

A substring is defined as a continuous segment of \(E\). Two substrings are considered different if they differ in position or length.

A substring is called magical if and only if:

• It is possible to transform it into a valid postfix expression by replacing every \(?\) with either \(\&\) or \(|\).
• Among these transformations, there exists at least one that evaluates to \(0\) and at least one that evaluates to \(1\).

Your task is to count the number of magical substrings.

inputFormat

The input consists of a single line containing the string \(E\), which comprises characters '0', '1', '|', '&', and '?'.

outputFormat

Output an integer representing the number of magical substrings.

sample

10?

1