{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThe Tower of Hanoi is a puzzle consisting of three pegs and a number of disks of different sizes which can slide onto any peg. The puzzle starts with the disks neatly stacked in order of size on one peg, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another peg, obeying the following rules:\u003c/p\u003e\u003cul\u003e\u003cli\u003eOnly one disk may be moved at a time.\u003c/li\u003e\u003cli\u003eEach move consists of taking the upper disk from one of the pegs and sliding it onto another peg, on top of the other disks that may already be present on that peg.\u003c/li\u003e\u003cli\u003eNo disk may be placed on top of a smaller disk.\u003c/li\u003e\u003c/ul\u003e\u003cp\u003eFor \u003ci\u003en\u003c/i\u003e disks, it is a well-known result that the optimal solution takes 2\u003csup\u003e\u003ci\u003en\u003c/i\u003e\u003c/sup\u003e − 1 moves.\u003c/p\u003e\u003cp\u003eTo complicate the puzzle a little, we allow multiple disks to be of the same size. Moreover, equisized disks are mutually distinguishable. Their ordering at the beginning should be preserved at the end, though it may be disturbed during the process of solving the puzzle.\u003c/p\u003e\u003cp\u003eGiven the number of disks of each size, compute the number of moves that the optimal solution takes.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input contains multiple test cases. Each test case consists of two lines. The first line contains two integers \u003ci\u003en\u003c/i\u003e and \u003ci\u003em\u003c/i\u003e (1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 100, 1 ≤ \u003ci\u003em\u003c/i\u003e ≤ 10\u003csup\u003e6\u003c/sup\u003e). The second lines contains \u003ci\u003en\u003c/i\u003e integers \u003ci\u003ea\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e, …, \u003ci\u003ea\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e (1 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e, …, \u003ci\u003ea\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e). For each 1 ≤ \u003ci\u003ei\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e, there are \u003ci\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e disks of size \u003ci\u003ei\u003c/i\u003e. The input ends where EOF is met.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, print the answer modulo \u003ci\u003em\u003c/i\u003e on a separate line.\u003c/p\u003e"}},{"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\u003e1 1000\r\n2\r\n5 1000\r\n1 1 1 1 1\r\n5 1000\r\n2 2 2 2 2\r\n5 1000\r\n1 2 1 2 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n31\r\n123\r\n41\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}