{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eChelsea is a modern artist. She decided to make her next work with ladders. She wants to combine some ladders and paint some beautiful pattern.\u003c/p\u003e\n\n\u003cp\u003eA ladder can be considered as a graph called \u003cem\u003ehashigo\u003c/em\u003e. There are \u003cstrong\u003en \u003c/strong\u003e\u003cem\u003ehashigos\u003c/em\u003e numbered from \u003cstrong\u003e0 \u003c/strong\u003eto \u003cstrong\u003en - 1\u003c/strong\u003e. \u003cem\u003eHashigo\u003c/em\u003e \u003cstrong\u003ei \u003c/strong\u003eof length \u003cstrong\u003el_i\u003c/strong\u003e has \u003cstrong\u003e2l_i + 6 \u003c/strong\u003evertices \u003cstrong\u003ev_\\{i,0\\\u003c/strong\u003e}, \u003cstrong\u003ev_\\{i,1\\\u003c/strong\u003e}, ..., \u003cstrong\u003ev_\\{i,2li+5\\\u003c/strong\u003e} and has edges between the pair of vertices (\u003cstrong\u003ev_\\{i,j\\\u003c/strong\u003e}, \u003cstrong\u003ev_\\{i,j+2\\\u003c/strong\u003e}) (\u003cstrong\u003e0 \u003c/strong\u003e≤ \u003cstrong\u003ej \u003c/strong\u003e≤ \u003cstrong\u003e2l_i + 3\u003c/strong\u003e) and (\u003cstrong\u003ev_\\{i,2j\\\u003c/strong\u003e}, \u003cstrong\u003ev_\\{i,2j+1\\\u003c/strong\u003e}) (\u003cstrong\u003e1 \u003c/strong\u003e≤ \u003cstrong\u003ej \u003c/strong\u003e≤ \u003cstrong\u003el_i + 1\u003c/strong\u003e). The gure below is example of a \u003cem\u003ehashigo\u003c/em\u003e of length \u003cstrong\u003e2\u003c/strong\u003e. This corresponds to the graph given in the first dataset in the sample input.\u003c/p\u003e\n\n\u003cp\u003e\u003cimg src\u003d\"https://static.e-olymp.com/content/5c/5cd2d4f737e7aa82ea7260774de4af0dc60a12d3.jpg\" /\u003e\u003c/p\u003e\n\n\u003cp\u003eTwo \u003cem\u003ehashigos \u003c/em\u003e\u003cstrong\u003ei \u003c/strong\u003eand \u003cstrong\u003ej \u003c/strong\u003eare combined at position \u003cstrong\u003ep \u003c/strong\u003e(\u003cstrong\u003e0 \u003c/strong\u003e≤ \u003cstrong\u003ep \u003c/strong\u003e≤ \u003cstrong\u003el_i - 1\u003c/strong\u003e) and \u003cstrong\u003eq \u003c/strong\u003e(\u003cstrong\u003e0 \u003c/strong\u003e≤ \u003cstrong\u003eq \u003c/strong\u003e≤ \u003cstrong\u003el_j - 1\u003c/strong\u003e) by marged each pair of vertices (\u003cstrong\u003ev_\\{i,2p+2\\\u003c/strong\u003e}, \u003cstrong\u003ev_\\{j,2q+2\\\u003c/strong\u003e}), (\u003cstrong\u003ev_\\{i,2p+3\\\u003c/strong\u003e}, \u003cstrong\u003ev_\\{j,2q+4\\\u003c/strong\u003e}), (\u003cstrong\u003ev_\\{i,2p+4\\\u003c/strong\u003e}, \u003cstrong\u003ev_\\{j,2q+3\\\u003c/strong\u003e}) and (\u003cstrong\u003ev_\\{i,2p+5\\\u003c/strong\u003e}, \u003cstrong\u003ev_\\{j,2q+5\\\u003c/strong\u003e}).\u003c/p\u003e\n\n\u003cp\u003eChelsea performs this operation \u003cstrong\u003en - 1 \u003c/strong\u003etimes to combine the \u003cstrong\u003en \u003c/strong\u003e\u003cem\u003ehashigos\u003c/em\u003e. After this operation, the graph should be connected and the maximum degree of the graph should not exceed \u003cstrong\u003e4\u003c/strong\u003e. The gure below is a example of the graph obtained by combining three \u003cem\u003ehashigos\u003c/em\u003e. This corresponds to the graph given in the second dataset in the sample input.\u003c/p\u003e\n\n\u003cp\u003e\u003cimg src\u003d\"https://static.e-olymp.com/content/4c/4cf0cccd462223cc3bf4d80be476fe679b1cefee.jpg\" /\u003e\u003c/p\u003e\n\n\u003cp\u003eNow she decided to paint each vertex by black or white with satisfying the following condition:\u003c/p\u003e\n\n\u003cul\u003e\n\u003cp\u003e\u003cli\u003e The maximum components formed by the connected vertices painted by the same color is less than or equals to \u003cstrong\u003ek\u003c/strong\u003e.\u003c/p\u003e\n\n\u003c/ul\u003e\n\n\u003cp\u003eShe would like to try all the patterns and choose the best. However, the number of painting way can be very huge. Since she is not good at math nor computing, she cannot calculate the number. So please help her with your superb programming skill!\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eInput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eThe input contains several datasets, and each dataset is in the following format.\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003en k\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003el_0 l_1 ... l_\\{n-1\\\u003c/strong\u003e}\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003ef_0 p_0 t_0 q_0\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003e...\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003ef_\\{n-2\\\u003c/strong\u003e p_\\{n-2\\} t_\\{n-2\\} q_\\{n-\\}2}\u003c/p\u003e\n\n\u003cp\u003eThe first line contains two integers \u003cstrong\u003en \u003c/strong\u003e(\u003cstrong\u003e1 \u003c/strong\u003e≤ \u003cstrong\u003en \u003c/strong\u003e≤ \u003cstrong\u003e30\u003c/strong\u003e) and \u003cstrong\u003ek \u003c/strong\u003e(\u003cstrong\u003e1 \u003c/strong\u003e≤ \u003cstrong\u003ek \u003c/strong\u003e≤ \u003cstrong\u003e8\u003c/strong\u003e).\u003c/p\u003e\n\n\u003cp\u003eThe next line contains \u003cstrong\u003en \u003c/strong\u003eintegers \u003cstrong\u003el_i\u003c/strong\u003e (\u003cstrong\u003e1 \u003c/strong\u003e≤ \u003cstrong\u003el_\\{i \\\u003c/strong\u003e}≤ \u003cstrong\u003e30\u003c/strong\u003e), each denotes the length of \u003cem\u003ehashigo \u003c/em\u003e\u003cstrong\u003ei\u003c/strong\u003e.\u003c/p\u003e\n\n\u003cp\u003eThe following \u003cstrong\u003en - 1 \u003c/strong\u003elines each contains four integers \u003cstrong\u003ef_i\u003c/strong\u003e (\u003cstrong\u003e0 \u003c/strong\u003e≤ \u003cstrong\u003ef_\\{i \\\u003c/strong\u003e}≤ \u003cstrong\u003en - 1\u003c/strong\u003e), \u003cstrong\u003ep_i\u003c/strong\u003e (\u003cstrong\u003e0 \u003c/strong\u003e≤ \u003cstrong\u003ep_\\{i \\\u003c/strong\u003e}≤ \u003cstrong\u003el_\\{fi-1\\\u003c/strong\u003e}), \u003cstrong\u003et_i \u003c/strong\u003e(\u003cstrong\u003e0 \u003c/strong\u003e≤ \u003cstrong\u003et_i\u003c/strong\u003e ≤ \u003cstrong\u003en - 1\u003c/strong\u003e), \u003cstrong\u003eq_i\u003c/strong\u003e (\u003cstrong\u003e0 \u003c/strong\u003e≤ \u003cstrong\u003eq_i\u003c/strong\u003e ≤ \u003cstrong\u003el_\\{ti-1\\\u003c/strong\u003e}). It represents the \u003cem\u003ehashigo \u003c/em\u003e\u003cstrong\u003ef_i\u003c/strong\u003e and the \u003cem\u003ehashigo \u003c/em\u003e\u003cstrong\u003et_i\u003c/strong\u003e are combined at the position \u003cstrong\u003ep_i\u003c/strong\u003e and the position \u003cstrong\u003eq_i\u003c/strong\u003e. You may assume that the graph obtained by combining \u003cstrong\u003en \u003c/strong\u003e\u003cem\u003ehashigos\u003c/em\u003e is connected and the degree of each vertex of the graph does not exceed \u003cstrong\u003e4\u003c/strong\u003e.\u003c/p\u003e\n\n\u003cp\u003eThe last dataset is followed by a line containing two zeros.\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eOutput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eFor each dataset, print the number of different colorings modulo \u003cstrong\u003e1000000007\u003c/strong\u003e in a line.\u003c/p\u003e\n\n"}},{"title":"Example","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\u003e1 5\n2\n3 7\n2 3 1\n0 1 1 0\n1 2 2 0\n2 8\n5 6\n0 2 1 2\n2 8\n1 1\n0 0 1 0\n2 2\n2 2\n0 1 1 0\n2 3\n3 3\n0 2 1 1\n2 4\n3 1\n1 0 0 1\n0 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e708\n1900484\n438404500\n3878\n496\n14246\n9768\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}