{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Alice and Bob want to secretly transmit messages to each other, and for this they have developed a random number generator (RNG), which is initialized with three integers: `a [0]`, `a [1]` and **n**. The first elements of the RNG are `a[0]` and `a[1] `, the following elements are constructed like this: `a[i+2]` \u003d (`a[i+1]` * `a[i+1]` + `a[i]` * `a[i]`) mod **n**, **i** \u003d **0**, **1**, ...\r\n\r\nAlice and Bob will use the RNG in the data transfer scheme, as shown in the figure.\r\n\r\n![prb4898](https://static.e-olymp.com/content/47/47893f9cd7cf016ba00cc6519ee4172ed678b28c.jpg)\r\n\r\nTo create a RNG, they want to write a procedure that calculates the value of `a[k]` for a given **k**. Help them!\r\n\r\n#### Input\r\nOne line contains four integers **n**, `a[0]`, `a[1]` and **k**, where **0** ≤ `a[k]`, `a[k]` \u003c **n** ≤ **200**, и **0** ≤ **k** ≤ `10^9`.\r\n\r\n#### Output\r\nPrint one number `a[k]`."}},{"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\u003e10 0 1 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\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\u003e10 2 4 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\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\u003e200 133 166 233266300\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e146\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}