Grid Paths

Grid Paths

There are 88418 paths in a 7×7 grid from the upper-left square to the lower-left square. Each path corresponds to a 48-character description consisting of characters D (down), U (up), L (left) and R (right).

For example, the path

corresponds to the description DRURRRRRDDDLUULDDDLDRRURDDLLLLLURULURRUULDLLDDDD.

You are given a description of a path which may also contain characters ? (any direction). Your task is to calculate the number of paths that match the description.

Input

The only input line has a 48-character string of characters ?, D, U, L and R.

Output

Print one integer: the total number of paths.

Example

Input:

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

Output:

201

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

bool visited[7][7];
string path;
int answer = 0;

inline bool valid(int i, int j) {

    if (i < 7 && j < 7 && i >= 0 && j >= 0 && ! visited[i][j]) {
        return true;
    }


    return false;
}

void dfs(int i, int j, int a) {
    //dbg(i, j, a);

    if (i == 6 && j == 0) {
        if (a == 48) {
            answer++;
        }
        return;
    }

    visited[i][j] = true;

    // go up
    if ((path[a] == 'U' || path[a] == '?')) {
        if (i > 0 && valid(i - 1, j)) {
            if (!(!valid(i - 2, j) && valid(i - 1, j - 1) && valid(i - 1, j + 1)) || (i - 1 == 6 && j == 0)) {
                dfs(i - 1, j, a + 1);
            }
        }
    }

    if (path[a] == 'D' || path[a] == '?') {
        if (i < 6 && valid(i + 1, j)) {
            if (!(!valid(i + 2, j) && valid(i + 1, j - 1) && valid(i + 1, j + 1))) {
                dfs(i + 1, j, a + 1);
            }
        }
    }

    if (path[a] == 'L' || path[a] == '?') {
        if (j > 0 && valid(i, j - 1)) {
            if (!(!valid(i, j - 2) && valid(i - 1, j - 1) && valid(i + 1, j - 1))) {
                dfs(i, j - 1, a + 1);
            }
        }
    }

    if (path[a] == 'R' || path[a] == '?') {
        if (j < 6 && valid(i, j + 1)) {
            if (!(!valid(i, j + 2)  && valid(i - 1, j + 1) && valid(i + 1, j + 1))) {
                dfs(i, j + 1, a + 1);
            }
        }
    }

    visited[i][j] = false;

    return;
}

int main() {
    re(path);
    dfs(0, 0, 0);
    cout << answer;
}