시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 110 33 20 30.303%

문제

다음과 같은 세가지 성질을 갖는 트리를 무한 이진 트리라고 한다.

  1. 모든 노드는 두 개의 자식 노드를 가지고 있다. 왼쪽 노드, 오른쪽 노드
  2. 어떤 노드의 번호가 X라면, 왼쪽 자식 노드의 번호는 2*X, 오른쪽 자식 노드의 번호는 2*X+1이다.
  3. 루트의 번호는 1이다.

무한 이진 트리를 탐색할 때는, 루트에서 시작한다. 그리고, 왼쪽 자식 또는 오른쪽 자식으로 이동하거나, 현재 노드에서 그대로 있을 수 있다.

탐색은 'L','R','P'로 이루어진 문자열로 표현할 수 있다.

  • 'L': 왼쪽 자식으로 이동
  • 'R': 오른쪽 자식으로 이동
  • 'P': 현재 노드에 그대로 있음

탐색의 값은 마지막으로 방문한 노드의 번호이다. 예를 들어, LR의 값은 5이고, RPP의 값은 3이다.

탐색의 집합은 'L','R','P','*'로 이루어진 문자열로 표현할 수 있다. '*'는 3개중 그 어떤 것이 될 수 있다.

탐색의 집합은 문자열과 일치하는 모든 패턴을 포함한다.

예를 들어, L*R은 LLR, LRR, LPR이며, **은 LL,LR,LP,RL,RR,RP,PL,PR,PP이다.

마지막으로, 탐색의 집합의 값은 탐색의 집합에 포함되어 있는 모든 탐색의 값의 합이다.

탐색의 집합의 문자열이 주어졌을 때, 탐색의 집합의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 탐색의 집합의 문자열이 주어진다. 이 문자열은 'L','R','P','*'로만 이루어져 있으며, 길이가 최대 10,000이다.

출력

첫째 줄에 탐색의 집합의 합을 출력한다.

예제 입력 1

P*P

예제 출력 1

6

힌트

W3sicHJvYmxlbV9pZCI6IjI5NjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzRcdWQ1NWMgXHVjNzc0XHVjOWM0IFx1ZDJiOFx1YjlhYyBcdWQwZDBcdWMwYzkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjMTM4XHVhYzAwXHVjOWMwIFx1YzEzMVx1YzljOFx1Yzc0NCBcdWFjMTZcdWIyOTQgXHVkMmI4XHViOWFjXHViOTdjIFx1YmIzNFx1ZDU1YyBcdWM3NzRcdWM5YzQgXHVkMmI4XHViOWFjXHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgXHViMTc4XHViNGRjXHViMjk0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjNzkwXHVjMmRkIFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM2N2NcdWNhYmQgXHViMTc4XHViNGRjLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHViMTc4XHViNGRjPFwvbGk+XHJcblx0PGxpPlx1YzViNFx1YjVhNCBcdWIxNzhcdWI0ZGNcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFhcdWI3N2NcdWJhNzQsIFx1YzY3Y1x1Y2FiZCBcdWM3OTBcdWMyZGQgXHViMTc4XHViNGRjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAyKlgsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM3OTBcdWMyZGQgXHViMTc4XHViNGRjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAyKlgrMVx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViOGU4XHVkMmI4XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAxXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YmIzNFx1ZDU1YyBcdWM3NzRcdWM5YzQgXHVkMmI4XHViOWFjXHViOTdjIFx1ZDBkMFx1YzBjOVx1ZDU2MCBcdWI1NGNcdWIyOTQsIFx1YjhlOFx1ZDJiOFx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCwgXHVjNjdjXHVjYWJkIFx1Yzc5MFx1YzJkZCBcdWI2MTBcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkIFx1Yzc5MFx1YzJkZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjNzBcdWIwOTgsIFx1ZDYwNFx1YzdhYyBcdWIxNzhcdWI0ZGNcdWM1ZDBcdWMxMWMgXHVhZGY4XHViMzAwXHViODVjIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQwZDBcdWMwYzlcdWM3NDAgJiMzOTtMJiMzOTssJiMzOTtSJiMzOTssJiMzOTtQJiMzOTtcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4mIzM5O0wmIzM5OzogXHVjNjdjXHVjYWJkIFx1Yzc5MFx1YzJkZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDk8XC9saT5cclxuXHQ8bGk+JiMzOTtSJiMzOTs6IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM3OTBcdWMyZGRcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5PFwvbGk+XHJcblx0PGxpPiYjMzk7UCYjMzk7OiBcdWQ2MDRcdWM3YWMgXHViMTc4XHViNGRjXHVjNWQwIFx1YWRmOFx1YjMwMFx1Yjg1YyBcdWM3ODhcdWM3NGM8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWQwZDBcdWMwYzlcdWM3NTggXHVhYzEyXHVjNzQwIFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YyBcdWJjMjlcdWJiMzhcdWQ1NWMgXHViMTc4XHViNGRjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgTFJcdWM3NTggXHVhYzEyXHVjNzQwIDVcdWM3NzRcdWFjZTAsIFJQUFx1Yzc1OCBcdWFjMTJcdWM3NDAgM1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMGQwXHVjMGM5XHVjNzU4IFx1YzlkMVx1ZDU2OVx1Yzc0MCAmIzM5O0wmIzM5OywmIzM5O1ImIzM5OywmIzM5O1AmIzM5OywmIzM5OyomIzM5O1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiAmIzM5OyomIzM5O1x1YjI5NCAzXHVhYzFjXHVjOTExIFx1YWRmOCBcdWM1YjRcdWI1YTQgXHVhYzgzXHVjNzc0IFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQwZDBcdWMwYzlcdWM3NTggXHVjOWQxXHVkNTY5XHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1YWNmYyBcdWM3N2NcdWNlNThcdWQ1NThcdWIyOTQgXHViYWE4XHViNGUwIFx1ZDMyOFx1ZDEzNFx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIEwqUlx1Yzc0MCBMTFIsIExSUiwgTFBSXHVjNzc0XHViYTcwLCAqKlx1Yzc0MCBMTCxMUixMUCxSTCxSUixSUCxQTCxQUixQUFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjLCBcdWQwZDBcdWMwYzlcdWM3NTggXHVjOWQxXHVkNTY5XHVjNzU4IFx1YWMxMlx1Yzc0MCBcdWQwZDBcdWMwYzlcdWM3NTggXHVjOWQxXHVkNTY5XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1ZDBkMFx1YzBjOVx1Yzc1OCBcdWFjMTJcdWM3NTggXHVkNTY5XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQwZDBcdWMwYzlcdWM3NTggXHVjOWQxXHVkNTY5XHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWQwZDBcdWMwYzlcdWM3NTggXHVjOWQxXHVkNTY5XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMGQwXHVjMGM5XHVjNzU4IFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwICYjMzk7TCYjMzk7LCYjMzk7UiYjMzk7LCYjMzk7UCYjMzk7LCYjMzk7KiYjMzk7XHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWNkNWNcdWIzMDAgMTAsMDAwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMGQwXHVjMGM5XHVjNzU4IFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5NjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTRVROSkEiLCJkZXNjcmlwdGlvbiI6IjxwPkluIGFuIGluZmluaXRlIGJpbmFyeSB0cmVlOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkVhY2ggbm9kZSBoYXMgZXhhY3RseSB0d28gY2hpbGRyZW4gJm5kYXNoOyBhIGxlZnQgYW5kIGEgcmlnaHQgY2hpbGQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPklmIGEgbm9kZSBpcyBsYWJlbGVkIHdpdGggdGhlIGludGVnZXIgWCwgdGhlbiBpdHMgbGVmdCBjaGlsZCBpcyBsYWJlbGVkIDImbWlkZG90O1ggYW5kIGl0cyByaWdodCBjaGlsZCAyJm1pZGRvdDtYKzEuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlRoZSByb290IG9mIHRoZSB0cmVlIGlzIGxhYmVsZWQgMS4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5BIHdhbGsgb24gdGhlIGJpbmFyeSB0cmVlIHN0YXJ0cyBpbiB0aGUgcm9vdC4gRWFjaCBzdGVwIGluIHRoZSB3YWxrIGlzIGVpdGhlciBhIGp1bXAgb250byB0aGUgbGVmdCBjaGlsZCwgb250byB0aGUgcmlnaHQgY2hpbGQsIG9yIHBhdXNlIGZvciByZXN0IChzdGF5IGluIHRoZSBzYW1lIG5vZGUpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BIHdhbGsgaXMgZGVzY3JpYmVkIHdpdGggYSBzdHJpbmcgb2YgbGV0dGVycyAmIzM5O0wmIzM5OywgJiMzOTtSJiMzOTsgYW5kICYjMzk7UCYjMzk7OiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiYjMzk7TCYjMzk7IHJlcHJlc2VudHMgYSBqdW1wIHRvIHRoZSBsZWZ0IGNoaWxkOyZuYnNwOzxcL2xpPlxyXG5cdDxsaT4mIzM5O1ImIzM5OyByZXByZXNlbnRzIGEganVtcCB0byB0aGUgcmlnaHQgY2hpbGQ7Jm5ic3A7PFwvbGk+XHJcblx0PGxpPiYjMzk7UCYjMzk7IHJlcHJlc2VudHMgYSBwYXVzZS4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgdmFsdWUgb2YgdGhlIHdhbGsgaXMgdGhlIGxhYmVsIG9mIHRoZSBub2RlIHdlIGVuZCB1cCBvbi4gRm9yIGV4YW1wbGUsIHRoZSB2YWx1ZSBvZiB0aGUgd2FsayBMUiBpcyA1LCB3aGlsZSB0aGUgdmFsdWUgb2YgdGhlIHdhbGsgUlBQIGlzIDMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkEgc2V0IG9mIHdhbGtzIGlzIGRlc2NyaWJlZCBieSBhIHN0cmluZyBvZiBjaGFyYWN0ZXJzICYjMzk7TCYjMzk7LCAmIzM5O1ImIzM5OywgJiMzOTtQJiMzOTsgYW5kICYjMzk7KiYjMzk7LiBFYWNoICYjMzk7KiYjMzk7IGNhbiBiZSBhbnkgb2YgdGhlIHRocmVlIG1vdmVzOyB0aGUgc2V0IG9mIHdhbGtzIGNvbnRhaW5zIGFsbCB3YWxrcyBtYXRjaGluZyB0aGUgcGF0dGVybi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHRoZSBzZXQgTCpSIGNvbnRhaW5zIHRoZSB3YWxrcyBMTFIsIExSUiBhbmQgTFBSLiBUaGUgc2V0ICoqIGNvbnRhaW5zIHRoZSB3YWxrcyBMTCwgTFIsIExQLCBSTCwgUlIsIFJQLCBQTCwgUFIgYW5kIFBQLiZuYnNwOzxcL3A+XHJcblxyXG48cD5GaW5hbGx5LCB0aGUgdmFsdWUgb2YgYSBzZXQgb2Ygd2Fsa3MgaXMgdGhlIHN1bSBvZiB2YWx1ZXMgb2YgYWxsIHdhbGtzIGluIHRoZSBzZXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkNhbGN1bGF0ZSB0aGUgdmFsdWUgb2YgdGhlIGdpdmVuIHNldCBvZiB3YWxrcy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkEgc3RyaW5nIGRlc2NyaWJpbmcgdGhlIHNldC4gT25seSBjaGFyYWN0ZXJzICYjMzk7TCYjMzk7LCAmIzM5O1ImIzM5OywgJiMzOTtQJiMzOTsgYW5kICYjMzk7KiYjMzk7IHdpbGwgYXBwZWFyIGFuZCB0aGVyZSB3aWxsIGJlIGF0IG1vc3QgMTAwMDAgb2YgdGhlbS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIHZhbHVlIG9mIHRoZSBzZXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==