Đường đi trên lưới

Bạn có một lưới \(7 \times 7\) với các ô \((r, c)\), \(1 \le r, c \le 7\). Bắt đầu từ ô \((1,1)\). Bạn nhận được một xâu \(s\) có đúng \(48\) ký tự, mỗi ký tự thuộc tập \(\{U, D, L, R, ?\}\), mô tả dãy di chuyển theo thứ tự:

• \(U\): đi lên một ô
• \(D\): đi xuống một ô
• \(L\): đi sang trái một ô
• \(R\): đi sang phải một ô
• \(?\): có thể chọn một trong bốn hướng trên.

Bạn không được rời khỏi lưới và không được đi vào một ô đã từng đi qua trước đó.

Hãy đếm số lượng đường đi hợp lệ có chính xác \(48\) bước, xuất phát từ \((1,1)\) và kết thúc tại \((7,1)\), sao cho tại mỗi bước, hướng đi phù hợp với ký tự tương ứng trong \(s\) (nếu là ? thì được chọn tự do).

\InputFile
Một dòng chứa xâu \(s\) dài \(48\) ký tự, mỗi ký tự thuộc \(\{U, D, L, R, ?\}\).

\OutputFile
In ra một số nguyên là số lượng đường đi thỏa mãn.

Example

????U???????????D???????????????????????????????

6665