{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":" \n \u003cp\u003eLong long ago, there lived some rabbits in forest. In the last day of the year, rabbit kingdom would hold a celebration for new year. Of course, rabbit king and his guards would take part in this celebration.\u003c/p\u003e \n \u003cp\u003eThe king had 2n+1 guards. At the beginning of celebration, just for fun, the king gave out some money to every guards. All guards were numbered from 1 to 2n+1, and the i-th guard get a\u003csub\u003ei\u003c/sub\u003e Yuan(a\u003csub\u003ei\u003c/sub\u003e is an integer in [0, m]).\u003c/p\u003e \n \u003cp\u003eAfter the celebration, in order to show his happiness, the king would give out x Yuan more to every guard. The king didn\u0027t want to give too much or too less, so he decided that x must be an integer in the interval [L, R]. The king liked number 0 very much, so he wanted that the xor sum of everybody\u0027s amount of money to be zero after the celebration. The king also wanted to know, under such circumstances, how many different ways could he do to give out the money before celebration.\u003c/p\u003e \n "}},{"title":"Input","value":{"format":"HTML","content":" \n \u003cp\u003eThere are no more than 12 test cases. \u003c/p\u003e \n \u003cp\u003eFor each test case, there is only one line containing four integers n, m, L and R. Their meanings are already mentioned above.\u003c/p\u003e \n \u003cp\u003e(1 \u0026lt;\u003d n, m \u0026lt;\u003d 1000, 1 \u0026lt;\u003d L \u0026lt;\u003d R \u0026lt;\u003d 1000)\u003c/p\u003e \n "}},{"title":"Output","value":{"format":"HTML","content":" \n \u003cp\u003eFor each test, print one line containing the answer modulo 1000000007\u003c/p\u003e \n "}},{"title":"Sample Input","value":{"format":"HTML","content":" \n \u003cpre\u003e1 3 1 3\r\n2 3 2 5\u003c/pre\u003e \n "}},{"title":"Sample Output","value":{"format":"HTML","content":" \n \u003cpre\u003e12\r\n120\u003c/pre\u003e \n "}}]}