Problem: In Takahashi's mind, there is always an integer sequence of length 2 \times 10^9 + 1: A = (A_{-10^9}, A_{-10^9 + 1}, ..., A_{10^9 - 1}, A_{10^9}) and an integer P.

Initially, all the elements in the sequence A in Takahashi's mind are 0, and the value of the integer P is 0.

When Takahashi eats symbols `+`, `-`, `>` and `<`, the sequence A and the integer P will change as follows:

* When he eats `+`, the value of A_P increases by 1;
* When he eats `-`, the value of A_P decreases by 1;
* When he eats `>`, the value of P increases by 1;
* When he eats `<`, the value of P decreases by 1.



Takahashi has a string S of length N. Each character in S is one of the symbols `+`, `-`, `>` and `<`. He chose a pair of integers (i, j) such that 1 \leq i \leq j \leq N and ate the symbols that are the i-th, (i+1)-th, ..., j-th characters in S, in this order. We heard that, after he finished eating, the sequence A became the same as if he had eaten all the symbols in S from first to last. How many such possible pairs (i, j) are there?

Constraints

* 1 \leq N \leq 250000
* |S| = N
* Each character in S is `+`, `-`, `>` or `<`.

Input

Input is given from Standard Input in the following format:


N
S


Output

Print the answer.

Examples

Input

5
+>+<-


Output

3


Input

5
+>+-<


Output

5


Input

48
-+><<><><><>>>+-<<>->>><<><<-+<>><+<<>+><-+->><<


Output

475

Solution (in CPP):

Solution:
#include<stdio.h>
#include<map>
using namespace std;
int k1[262144],b1[262144],k2[262144],b2[262144];
char s[262144];
map<long long,int> qaq;
int main()
{
	int n;
	scanf("%d",&n);
	scanf("%s",s+1);
	k1[0]=1;
	b1[0]=0;
	k2[0]=1;
	b2[0]=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='+')
		{
			k1[i]=k1[i-1];
			b1[i]=b1[i-1]+k1[i-1];
			if(b1[i]>=998244353)
			{
				b1[i]-=998244353;
			}
			k2[i]=k2[i-1];
			b2[i]=b2[i-1]+k2[i-1];
			if(b2[i]>=1000000007)
			{
				b2[i]-=1000000007;
			}
		}
		else if(s[i]=='-')
		{
			k1[i]=k1[i-1];
			b1[i]=b1[i-1]-k1[i-1];
			if(b1[i]<0)
			{
				b1[i]+=998244353;
			}
			k2[i]=k2[i-1];
			b2[i]=b2[i-1]-k2[i-1];
			if(b2[i]<0)
			{
				b2[i]+=1000000007;
			}
		}
		else if(s[i]=='>')
		{
			k1[i]=(long long)k1[i-1]*19260817%998244353;
			b1[i]=b1[i-1];
			k2[i]=(long long)k2[i-1]*19491001%1000000007;
			b2[i]=b2[i-1];
		}
		else
		{
			k1[i]=(long long)k1[i-1]*494863259%998244353;
			b1[i]=b1[i-1];
			k2[i]=(long long)k2[i-1]*301354971%1000000007;
			b2[i]=b2[i-1];
		}
	}
	long long ans=0;
	for(int i=0;i<=n;i++)
	{
		ans+=qaq[(long long)b1[i]*1000000007+b2[i]];
		int val1=((long long)k1[i]*b1[n]+b1[i])%998244353;
		int val2=((long long)k2[i]*b2[n]+b2[i])%1000000007;
		qaq[(long long)val1*1000000007+val2]++;
	}
	printf("%lld\n",ans);
	return 0;
}