Это сложная версия задачи F. Единственное различие между простой и сложной версиями заключается в ограничениях.

Будем называть непустую строку сбалансированной, если она содержит одинаковое количество знаков плюс и минус. Например: строки «+--+» и «++-+--» являются сбалансированными, а строки «+--», «--» и «» не являются сбалансированными.

Будем называть строку перспективной, если строку можно сделать сбалансированной при помощи нескольких(возможно нуля) применений следующей операции:

• заменим два соседних знака минуса на один знак плюс.

В частности, всякая сбалансированная строка является перспективной. Однако обратное неверно: не всякая перспективная строка — сбалансирована.

Например: строка «-+---» является перспективной, так как можно заменить два соседних минуса на плюс и получить сбалансированную строку «-++-», либо получить другую сбалансированную строку «-+-+».

Сколько непустых подстрок данной строки $$$s$$$ являются перспективными? Каждая непустая перспективная подстрока должна быть учтена в ответе столько раз, сколько раз она встречается в строке $$$s$$$.

Напомним, что подстрока — это последовательность подряд идущих символов строки. Например, для строки «+-+» её подстроками являются строки «+-», «-+», «+», «+-+» (строка является подстрокой самой себя) и некоторые другие. Но следующие строки её подстроками не являются: «--», «++», «-++».