{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"There is a huge **2 x N** board, six types of tiles are available, and each of them is infinitely many, you have to find the number of ways you can fill the board using the tiles. Two board configurations are different if at least in one cell, their colors differ. The tiles are given below:\n\n\n\n| ![Type 1][1] | ![Type 2][2] | ![Type 3][3] | ![Type 4][4] | ![Type 5][5] | ![Type 6][6] |\n| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |\n\n\n\nYou **cannot** rotate or flip any tile. And no cell in the board should be empty. The tiles shouldn\u0027t overlap.\n\nFor example, a **2 x 3** board can be colored by **5** ways, they are:\n\n\n\n| ![Combination 1][7] | ![Combination 2][8] | ![Combination 3][9] | ![Combination 4][10] | ![Combination 5][11] |\n| :-----------------: | :-----------------: | :-----------------: | :------------------: | :------------------: |\n\n\n\n[1]: https://static.lightoj.com/images/problem-1271-tiles_ii_1-1605689158345.png\n[2]: https://static.lightoj.com/images/problem-1271-tiles_ii_2-1605689174196.png\n[3]: https://static.lightoj.com/images/problem-1271-tiles_ii_3-1605689185856.png\n[4]: https://static.lightoj.com/images/problem-1271-tiles_ii_4-1605689204279.png\n[5]: https://static.lightoj.com/images/problem-1271-tiles_ii_5-1605689216245.png\n[6]: https://static.lightoj.com/images/problem-1271-tiles_ii_6-1605689230034.png\n\n[7]: https://static.lightoj.com/images/problem-1271-tiles_ii_comb_1-1605689482194.png\n[8]: https://static.lightoj.com/images/problem-1271-tiles_ii_comb_2-1605689495863.png\n[9]: https://static.lightoj.com/images/problem-1271-tiles_ii_comb_3-1605689506894.png\n[10]: https://static.lightoj.com/images/problem-1271-tiles_ii_comb_4-1605689517670.png\n[11]: https://static.lightoj.com/images/problem-1271-tiles_ii_comb_5-1605689530270.png"}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 10000)**, denoting the number of test cases.\n\nEach case starts with a line containing an integer **N (1 \u0026le; N \u0026le; 10\u003csup\u003e9\u003c/sup\u003e)**."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the number of ways the board can be colored. The number may be large, so, output the number modulo **10007 (10\u003csup\u003e4\u003c/sup\u003e + 7)**."}},{"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\u003e5\n3\n10\n20\n100\n87\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 5\nCase 2: 1255\nCase 3: 6239\nCase 4: 6542\nCase 5: 5502\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}