{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eYou are given a recurrent formula for a sequence \u003ci\u003ef\u003c/i\u003e:\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_center\"\u003e\u003ci\u003ef\u003c/i\u003e(\u003ci\u003en\u003c/i\u003e) \u003d 1 + \u003ci\u003ef\u003c/i\u003e(1)\u003ci\u003eg\u003c/i\u003e(1) + \u003ci\u003ef\u003c/i\u003e(2)\u003ci\u003eg\u003c/i\u003e(2) + … + \u003ci\u003ef\u003c/i\u003e(\u003ci\u003en\u003c/i\u003e−1)\u003ci\u003eg\u003c/i\u003e(\u003ci\u003en\u003c/i\u003e−1), \r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003ewhere \u003ci\u003eg\u003c/i\u003e is also a recurrent sequence given by formula\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_center\"\u003e\u003ci\u003eg\u003c/i\u003e(\u003ci\u003en\u003c/i\u003e) \u003d 1 + 2\u003ci\u003eg\u003c/i\u003e(1) + 2\u003ci\u003eg\u003c/i\u003e(2) + 2\u003ci\u003eg\u003c/i\u003e(3) + … + 2\u003ci\u003eg\u003c/i\u003e(\u003ci\u003en\u003c/i\u003e−1) − \u003ci\u003eg\u003c/i\u003e(\u003ci\u003en\u003c/i\u003e−1)\u003ci\u003eg\u003c/i\u003e(\u003ci\u003en\u003c/i\u003e−1).\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIt is known that \u003ci\u003ef\u003c/i\u003e(1)\u0026nbsp;\u003d\u0026nbsp;1, \u003ci\u003eg\u003c/i\u003e(1)\u0026nbsp;\u003d\u0026nbsp;1. \r\nYour task is to find \u003ci\u003ef\u003c/i\u003e(\u003ci\u003en\u003c/i\u003e)\u0026nbsp;mod\u0026nbsp;\u003ci\u003ep\u003c/i\u003e.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe input consists of several cases. Each case contains two\r\nnumbers on a single line. These numbers are \u003ci\u003en\u003c/i\u003e (1\u0026nbsp;≤\u0026nbsp;\u003ci\u003en\u003c/i\u003e\u0026nbsp;≤\u0026nbsp;10000) and\r\n\u003ci\u003ep\u003c/i\u003e (2\u0026nbsp;≤\u0026nbsp;\u003ci\u003ep\u003c/i\u003e\u0026nbsp;≤\u0026nbsp;2·10\u003csup\u003e9\u003c/sup\u003e).\r\nThe input is terminated by the case with \u003ci\u003en\u003c/i\u003e \u003d \u003ci\u003ep\u003c/i\u003e \u003d 0 which should not be\r\nprocessed. The number of cases in the input does not exceed 5000.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOutput for each case the answer to the task on a separate line.\r\n\u003c/div\u003e\u003c/div\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 2\r\n2 11\r\n0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}