Có tất cả \(88418\) đường đi trên một lưới ô vuông \(7 \times 7\) từ ô ở góc trái, bên trên xuống ô góc trái, bên dưới. Mỗi đường đi tương ứng với một xâu mô tả gồm \(48\) kí tự, bao gồm các kí tự D (xuống), U (lên), L (trái), R (phải).

Ví dụ, đường đi

tương ứng với xâu DRURRRRRDDDLUULDDDLDRRURDDLLLLLURULURRUULDLLDDDD.

Bạn được cho trước một xâu mô tả đường đi, mà trong đó có chứa cả kí tự ? (đi hướng nào cũng được). Nhiệm vụ của bạn là tính số lượng đường đi khớp với xâu mô tả này.

Input

• Dòng đầu vào duy nhất có một xâu \(48\) ký tự gồm các ký tự ?, D, U, L và R.

Output

• In ra một số nguyên: tổng số đường đi.

Example

Sample input

??????R??????U??????????????????????????LD????D?

Sample output

201