Có tất cả \(88418\) đường đi trên bảng ô vuông kích thước \(7\times7\) từ ô vuông ở góc trên bên trái xuống ô vuông góc dưới bên trái. Mỗi đường đi được mô tả bởi một chuỗi \(48\) ký tự bao gồm: D (xuống), U (lên), L (trái) and R (phải).

Ví dụ đường đi sau:

được mô tả bằng chuỗi ký tự sau: DRURRRRRDDDLUULDDDLDRRURDDLLLLLURULURRUULDLLDDDD.

Bạn được cho một chuỗi \(48\) ký tự mô tả đường đi, trong đó có chứa một số ký tự ? (đi bất cứ hướng nào). Nhiệm vụ của bạn là tính số đường đi có thể tương ứng với mô tả đó.

Input

• Gồm một dòng có \(48\) ký tự liền nhau, bao gồm: ?, D, U, L và R.

Output

• In ra một số nguyên duy nhất: Số đường đi.

Ví dụ

Sample input

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

Sample output

201