[伯俊]探索2963無限バイナリツリー

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

typedef unsigned long long ull;

ull sum = 0;
string input;

void bfs() {

	//<node, index>
	queue<pair<ull, int>> q;
	q.push(make_pair(1, 0));

	while (!q.empty()) {
		pair<ull, int> cur = q.front();
		ull curnode = cur.first;
		int curindex = cur.second;
		q.pop();

		//bfs 횟수 줄이기 위해 * 만날 때 까지 while문 반복
		while (curindex < input.size()) {
			if (input[curindex] == 'L')
				curnode = curnode << 1;
			if (input[curindex] == 'P')
				curnode = curnode;
			if (input[curindex] == 'R')
				curnode = (curnode << 1) + 1;
			if (input[curindex] == '*')
				break;

			++curindex;
		}

		//base case
		if (curindex == input.size()) {
			sum += curnode;
			continue;
		}

		//bfs
		q.push(make_pair(curnode << 1, curindex + 1));
		q.push(make_pair(curnode, curindex + 1));
		q.push(make_pair((curnode << 1) + 1, curindex + 1));
	}

}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> input;

	bfs();

	cout << sum;
	return 0;
}