An architect wants to decorate one of his buildings with a long, thin mosaic. He has two kinds of tiles available to him, each 2 inches by 2 inches:
There will be several test cases. Each test case will consist of two integers on a single line, N and M (2 ≤ N ≤ 10, 2 ≤ M ≤ 500). These represent the dimensions of the strip he wishes to fill, in inches. The data set will conclude with a line with two 0's.
For each test case, print out a single integer representing the number of unique ways that the architect can tile the space, modulo 106. Print each integer on its own line, with no extra whitespace. Do not print any blank lines between answers.
2 10 4 16 4 50 0 0
25 366318 574777