ძროხის ძებნა

დროის ლიმიტი: 2 წმ

მეხსიერების ლიმიტი: 512 მეგაბაიტი

შემავალი მონაცემები: cin

გამომავალი მონაცემები: cout


ძროხა ბესი გაიქცა და იმალება მაღალი ბალახით დაფარულ გორაკზე. ფერმერმა ჯონმა გადაწყვიტა, რომ შეუმჩნევლად მიეპაროს და ამისათვის აპირებს, რომ ბალახებში ხოხვით მიუახლოვდეს. ბალახები ჯონის თვალწინ ჩანს, როგორც N (1<=N<=50,000) ცალი ფრჩხილისაგან შემდგარი სტრიქონი. მაგალითად ასეთი: )((()())()) ჯონმა იცის, რომ ბესის უკანა ფეხები წააგავს ორ მეზობელ გახსნილ ფრჩხილს ((, ხოლო მისი წინა ფეხები კი - ორ მეზობელ დახურულ ფრჩხილს )). ბესი შეიძლება მდებარეობდეს ნებისმიერ ადგილზე, რომელიც განისაზღვრება, როგორც წინა და უკანა ფეხების წყვილი. გამოთვალეთ ასეთ შესაძლო მდებარეობათა რაოდენობა.

 

შეტანის ფორმატი:

* სტრიქონი 1: N (1<=N<=50,000) ფრჩხილისაგან შედგენილი სტრიქონი.

 

გამოტანის ფორმატი:

* სტრიქონი 1: ბესის შესაძლო მდებარეობათა რაოდენობა.




მაგალითები

შესატანი მონაცემები
)((()())()) დაკოპირება
გამოსატანი მონაცემები
4 დაკოპირება

შენიშვნა

აქ ბესის შესაძლო მდებარეობათა რაოდენობაა 4.

იხილეთ სურათები ქვემოთ:

 

  ) ( ( ( ) ( ) ) ( ) )
1   ^ ^       ^ ^      
2     ^ ^     ^ ^      
3     ^ ^           ^ ^
4   ^ ^             ^ ^