{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\r\n\t\u003cdiv\u003e\r\n\t\t\u0026quot;It is so sweet to have chocolates on St. Valentine\u0026#39;s Day!\u0026quot; Little \u003cspan data-scayt_word\u003d\"Facer\" data-scaytid\u003d\"6\"\u003eFacer\u003c/span\u003e was so excited when he receives a box of self-made chocolates from his girlfriend, and he decided to eat these chocolates in a special way to commemorate this important day. Suppose that there are \u003ci\u003eN\u003c/i\u003e types of chocolates in the box, it can be easily calculated that there are totally \u0026nbsp;C(N, 3)\u0026nbsp;different combinations if we choose 3 chocolates of different types to make a dish. \u003cspan data-scayt_word\u003d\"Facer\" data-scaytid\u003d\"49\"\u003eFacer\u003c/span\u003e will first make one dish for every of these combination, so there will be C(N, 3) dishes in all with 3\u0026times;C(N, 3)\u0026nbsp;chocolates totally. Then both \u003cspan data-scayt_word\u003d\"Facer\" data-scaytid\u003d\"8\"\u003eFacer\u003c/span\u003e and his girlfriend choose some chocolates of different types as their original chocolates set. After that, \u003cspan data-scayt_word\u003d\"Facer\" data-scaytid\u003d\"9\"\u003eFacer\u003c/span\u003e choose exactly \u003ci\u003eM\u003c/i\u003e dishes of three-type-mixed-chocolates which he made in the first step and add them into his original chocolates set. Finally, \u003cspan data-scayt_word\u003d\"Facer\" data-scaytid\u003d\"10\"\u003eFacer\u003c/span\u003e continues \u003cspan data-scayt_word\u003d\"eatting\" data-scaytid\u003d\"1\"\u003eeatting\u003c/span\u003e two chocolates of the same type until he cannot find any pair of chocolates of the same type (which means for each type of chocolates, there remains at most one chocolate). \u003cspan data-scayt_word\u003d\"Facer\" data-scaytid\u003d\"11\"\u003eFacer\u003c/span\u003e wishes that his remaining chocolates set could be identical with his girlfriend\u0026#39;s original chocolates set after the steps mentioned above, but he does not know the number of ways to choose dishes. Could please tell him the answer?\u003c/div\u003e\r\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\r\n\t\u003cdiv\u003e\r\n\t\tThe input consists of multiple test cases. Each test case starts with two integers, \u003ci\u003eN\u003c/i\u003e and \u003ci\u003eM\u003c/i\u003e, which are the number of different types of chocolates and the number of three-type-mixed-chocolates dishes \u003cspan data-scayt_word\u003d\"Facer\" data-scaytid\u003d\"2\"\u003eFacer\u003c/span\u003e will choose, it is guaranteed that \u003cspan data-scayt_word\u003d\"1≤N≤1000\" data-scaytid\u003d\"3\"\u003e1\u0026le;\u003ci\u003eN\u003c/i\u003e\u0026le;1000\u003c/span\u003e, \u003cspan data-scayt_word\u003d\"0≤M≤1000\" data-scaytid\u003d\"4\"\u003e0\u0026le;\u003ci\u003eM\u003c/i\u003e\u0026le;1000\u003c/span\u003e. The following two lines contain one \u003ci\u003eN\u003c/i\u003e-bit binary integer each, which represents \u003cspan data-scayt_word\u003d\"Facer\u0027s\" data-scaytid\u003d\"5\"\u003eFacer\u0026#39;s\u003c/span\u003e and his girlfriend\u0026#39;s original chocolates set. A case with \u003ci\u003eN\u003c/i\u003e\u003d0 and \u003ci\u003eM\u003c/i\u003e\u003d0 indicates the end of the input file, which should not be processed.\u003c/div\u003e\r\n\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\r\n\t\u003cdiv\u003e\r\n\t\tFor each test case, print one line containing one single integer, which represents the total number of ways to choose dishes. Since the number can be extremely big, you are only required to output the answer % 10007.\u003c/div\u003e\r\n\u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e\r\n4 3\r\n1101\r\n1001\r\n3 1\r\n101\r\n010\r\n5 3\r\n11010\r\n10111\r\n0 0\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e\r\n1\r\n1\r\n6\r\n\u003c/pre\u003e"}}]}