{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"You have found a strange puzzle that looks like a full binary tree of height **n** (there are **n** nodes on the path from the root to any leaf). Nodes of the tree are numbered in the following way: the root node has number **1**, any node **x** which is not a leaf has two children with numbers **2x** (let\u0027s call it left child) and **2x** + **1** (right child).\r\n\r\nEach node has its own state which can be **0** or **1**. You can alter the states by starting a flipping reaction from any node. The flipping reaction then proceeds as follows. Firstly, the state of the node being flipped is changed to the opposite. After that, if this node is not a leaf, a chain reaction continues with one of its children: if the state of the node was 0 before the flip, the flipping reaction continues with its left child, and in the other case, with its right child. Thus the flipping reaction proceeds along a path from the starting node to exactly one leaf.\r\n\r\nAfter starting a flipping reaction from some node, you should wait until the whole reaction is finished before starting the next one. Each node can be the starting node of a flipping reaction any number of times.\r\n\r\nYou are given the initial states of all nodes. Your goal is to set all states to **0** by starting the minimal possible number of flipping reactions.\r\n\r\nAs the number of nodes can be very large, we can not directly give the states in the input file. Luckily, you can get all states using the following algorithm: in the input you are given integers **a**, **b**, **c**, **p** and **T**, where **p** is prime and **b** is positive. Using these numbers, you can generate the sequence `x[i]`:\r\n\r\n`x[1] \u003d a`\r\n\r\n`x[i]` \u003d (`x[i-1]` ∙ **b** + **c**) mod **p**, где **i** \u003e **1**\r\n\r\nFor each node **i**, if `x[i]` ≥ **T**, the initial state of **i**-th node is **1**, otherwise it\u0027s **0**.\r\n\r\n#### Input\r\nThe only line contains six integers **n**, **a**, **b**, **c**, **p** and **T** (**1** ≤ **n** ≤ **60**, **0** ≤ **a** \u003c **p**, **1** ≤ **b** \u003c **p**, **0** ≤ **c** \u003c **p**, **2** ≤ **p** ≤ `10^6`, **0** \u003c **T** \u003c **p**). It is guaranteed that **p** is prime.\r\n\r\n#### Output\r\nPrint the minimal possible number of flipping reactions needed to set the state of all nodes to **0**."}},{"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\u003e3 3 2 1 5 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\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\u003e4 4 1 0 7 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}