Саша спокойной программировал, пока к нему не подошла Валентина и не попросила объяснить, зачем в коде нужны все эти круглые скобки. Он объяснил ей их назначение в общих чертах и дал задание, чтобы успеть закончить работу в срок.

В этой задаче мы будет рассматривать только строки, состоящие из открывающих и закрывающих круглых скобок, то есть символов «(» и «)».

Последовательность скобок называется правильной в следующих случаях:

1. Если она пустая;
2. Если она состоит из правильной скобочной последовательности, заключённой между парой из открывающей скобки и закрывающей скобки;
3. Если она состоит из двух правильных скобочных последовательностей, записанных одна за другой.

Например, последовательности круглых скобок «()()» и «((()))(())» являются правильными, а «)(()», «(((((» и «())» — нет.

Саша взял листок и написал на нём некоторую строку s, состоящую только из открывающих и закрывающих круглых скобок, и попросил Валентину посчитать количество различных непустых подстрок строки s, являющихся правильными скобочными последовательностями. Другими словами, её задача состоит в том, чтобы посчитать количество непустых правильных скобочных последовательностей, встречающихся в s в качестве подстроки (не путать с подпоследовательностью).

Когда Валентина закончила выполнять задание, Саша вдруг осознал, что сам не знает ответа. Помогите ему не ударить в грязь лицом и решите задачу!