드래곤 패턴

드래곤 곡선은 길이가 1인 선분을 이어 붙인 꺾은선이고, 재귀적으로 정의한다. 평면 위의 한 점과 좌표축에 평행한 네 방향 중 하나를 정한 다음, 차수 $n$의 왼쪽(오른쪽) 드래곤을 이렇게 그린다.

• $n$이 0이면 현재 점에서 현재 방향으로 길이 1인 선분을 그리고 그 끝점으로 이동한다.
• 그렇지 않으면 현재 점에서 현재 방향으로 차수 $n-1$의 왼쪽 드래곤을 그리고, 끝점에서 왼쪽(오른쪽)으로 90도 돌린 뒤, 차수 $n-1$의 오른쪽 드래곤을 그린다.

원점 $(0, 0)$에서 $OX$축의 양의 방향으로 출발해 차수 $n$의 왼쪽 드래곤을 그린다. 길이 1인 이동이 차례로 $2^n$번 일어나므로, 이동 방향을 순서대로 적으면 길이 $2^n$인 문자열이 된다.

패턴도 이동 방향을 차례로 나열한 문자열이다. 이 방향 문자열에서 패턴과 같은 부분 문자열이 몇 개인지, 즉 패턴이 시작하는 위치가 몇 개인지 구하여라.

정수 $n$과 패턴을 나타내는 문자열 $S$가 공백 하나를 사이에 두고 한 줄로 주어진다. $S$는 문자 R, L, U, D로만 이루어진다. R은 오른쪽 이동($OX$축의 양의 방향), L은 왼쪽 이동($OX$축의 음의 방향), U는 위쪽 이동($OY$축의 양의 방향), D는 아래쪽 이동($OY$축의 음의 방향)을 뜻한다.

$0 \le n \le 10^9$, $1 \le |S| \le 10^6$이다.

$OX$축의 양의 방향으로 그린 차수 $n$의 왼쪽 드래곤에서 패턴 $S$가 나타나는 횟수를 $10^9+7$로 나눈 나머지를 출력한다.