{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/8e73a06ac7043a44c7cd3e24905926c1?v\u003d1714389499\"\u003e\u003c/center\u003e \u003cbr\u003e\u0026nbsp;\u0026nbsp;On the beaming day of 60th anniversary of NJUST, as a military college which was Second Artillery Academy of Harbin Military Engineering Institute before, queue phalanx is a special landscape.\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u003cbr\u003e\u0026nbsp;\u0026nbsp;Here is a M*N rectangle, and this one can be divided into M*N squares which are of the same size. As shown in the figure below:\u003cbr\u003e\u0026nbsp;\u0026nbsp;01--02--03--04\u003cbr\u003e\u0026nbsp;\u0026nbsp;|| || || ||\u003cbr\u003e\u0026nbsp;\u0026nbsp;05--06--07--08\u003cbr\u003e\u0026nbsp;\u0026nbsp;|| || || ||\u003cbr\u003e\u0026nbsp;\u0026nbsp;09--10--11--12\u003cbr\u003e\u0026nbsp;\u0026nbsp;Consequently, we have (M+1)*(N+1) nodes, which are all connected to their adjacent nodes. And actual queue phalanx will go along the edges.\u003cbr\u003e\u0026nbsp;\u0026nbsp;The ID of the first node,the one in top-left corner,is 1. And the ID increases line by line first ,and then by column in turn ,as shown in the figure above.\u003cbr\u003e\u0026nbsp;\u0026nbsp;For every node,there are two viable paths:\u003cbr\u003e\u0026nbsp;\u0026nbsp;(1)go downward, indicated by \u0027D\u0027;\u003cbr\u003e\u0026nbsp;\u0026nbsp;(2)go right, indicated by \u0027R\u0027;\u003cbr\u003e\u0026nbsp;\u0026nbsp;The current mission is that, each queue phalanx has to walk from the left-top node No.1 to the right-bottom node whose id is (M+1)*(N+1).\u003cbr\u003e In order to make a more aesthetic marching, each queue phalanx has to conduct two necessary actions. Let\u0027s define the action:\u003cbr\u003e\u0026nbsp;\u0026nbsp;An action is started from a node to go for a specified travel mode.\u003cbr\u003e\u0026nbsp;\u0026nbsp;So, two actions must show up in the way from 1 to (M+1)*(N+1).\u003cbr\u003e\u003cbr\u003e\u0026nbsp;\u0026nbsp;For example, as to a 3*2 rectangle, figure below:\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;01--02--03--04\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;|| || || ||\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;05--06--07--08\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;|| || || ||\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;09--10--11--12\u003cbr\u003e\u0026nbsp;\u0026nbsp;Assume that the two actions are (1)RRD (2)DDR\u003cbr\u003e\u003cbr\u003e\u0026nbsp;\u0026nbsp;As a result , there is only one way : RRDDR. Briefly, you can not find another sequence containing these two strings at the same time.\u003cbr\u003e\u0026nbsp;\u0026nbsp;If given the N, M and two actions, can you calculate the total ways of walking from node No.1 to the right-bottom node ?\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u0026nbsp;\u0026nbsp;The first line contains a number T,(T is about 100, including 90 small test cases and 10 large ones) denoting the number of the test cases.\u003cbr\u003e\u0026nbsp;\u0026nbsp;For each test cases,the first line contains two positive integers M and N(For large test cases,1\u0026lt;\u003dM,N\u0026lt;\u003d100, and for small ones 1\u0026lt;\u003dM,N\u0026lt;\u003d40). M denotes the row number and N denotes the column number.\u003cbr\u003e\u0026nbsp;\u0026nbsp;The next two lines each contains a string which contains only \u0027R\u0027 and \u0027D\u0027. The length of string will not exceed 100. We ensure there are no empty strings and the two strings are different.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u0026nbsp;\u0026nbsp;For each test cases,print the answer MOD 1000000007 in one line.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n3 2\r\nRRD\r\nDDR\r\n3 2\r\nR\r\nD\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n10\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}