{"code":"btree","name":"Cây nhị phân (OLP 11 - 2018)","description":"Cho 2 xâu ký tự $S$ và $T$ trong đó nếu xâu nào khác rỗng thì chỉ gồm các ký tự thuộc tập hợp {$‘U’,‘L’, ‘R’$}.\r\n\r\nXét một cây nhị phân vô hạn, mỗi nút trên cây có đúng một nút cha và hai nút con (nút cha của nút\r\ngốc là chính nó). Xuất phát từ nút gốc, ta có thể di chuyển trên cây đã cho nhờ xâu $S$ bằng cách\r\nduyệt lần lượt các ký tự của xâu $S$ theo quy tắc: $‘L’$ là chuyển sang nút con trái, $‘R’$ là sang nút con\r\nphải và $‘U’$ là chuyển về nút cha. Quá trình này kết thúc tại nút nào đó $X$. Đương nhiên, nếu $S$ là\r\nxâu rỗng thì $X$ chính là nút gốc.\r\n\r\nKý hiệu $\\Omega$ là tập hợp tất cả các xâu con của xâu $T$ (mỗi xâu con của $T$ nhận được từ $T$ bằng cách\r\nxoá bỏ một số tuỳ ý các ký tự của nó; xâu rỗng và bản thân $T$ đều là xâu con của $T$).\r\n\r\n**Yêu cầu**: Hãy cho biết số nút khác nhau trên cây có thể di chuyển đến được, bắt đầu từ nút $X$, bằng\r\ncách di chuyển trên cây nhờ tất cả các xâu trong $\\Omega$.\r\n\r\n

Input

\r\n\r\n- Dòng đầu ghi số nguyên $T (T \\le 50)$, là số lượng bộ dữ liệu vào.\r\n- Mỗi bộ dữ liệu vào gồm 2 dòng liên\r\ntiếp trong đó mỗi dòng bắt đầu bằng ký\r\ntự ‘#’ và tiếp theo là xâu $S$ (dòng đầu)\r\nhoặc xâu $T$ (dòng tiếp theo). Độ dài\r\nmỗi xâu $S, T$ đều không vượt quá\r\n$100000 (10^5)$.\r\n\r\n\r\n

Output

\r\n\r\n- Ghi ra các số nguyên, mỗi số trên một dòng, là kết quả\r\ntìm được tương ứng với bộ dữ liệu vào. Các\r\nkết quả cần được lấy là dư của phép chia cho\r\n$100000000 (10^8)$.\r\n\r\n

Scoring

\r\n\r\n - Subtask $1$ ($30\\%$ số điểm): tổng độ dài các xâu $S$ và $T$ không vượt quá $22$.\r\n - Subtask $2$ ($50\\%$ số điểm): xâu $S$ là xâu rỗng (độ dài bằng 0).\r\n - Subtask $3$ ($20\\%$ số điểm): Không cỏ ràng buộc gì thêm.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 5\r\n #\r\n #LL\r\n #LR\r\n #\r\n #LU\r\n #RLL\r\n #\r\n #\r\n #LR\r\n #RLUL\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 3\r\n 1\r\n 6\r\n 1\r\n 8\r\n ```","points":300.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}