{"raw_statement":[{"iden":"problem statement","content":"Let us denote by $f(x, m)$ the remainder of the Euclidean division of $x$ by $m$.\nLet $A$ be the sequence that is defined by the initial value $A_1=X$ and the recurrence relation $A_{n+1} = f(A_n^2, M)$. Find $\\displaystyle{\\sum_{i=1}^N A_i}$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^{10}$\n*   $0 \\leq X < M \\leq 10^5$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $X$ $M$"},{"iden":"sample input 1","content":"6 2 1001"},{"iden":"sample output 1","content":"1369\n\nThe sequence $A$ begins $2,4,16,256,471,620,\\ldots$ Therefore, the answer is $2+4+16+256+471+620=1369$."},{"iden":"sample input 2","content":"1000 2 16"},{"iden":"sample output 2","content":"6\n\nThe sequence $A$ begins $2,4,0,0,\\ldots$ Therefore, the answer is $6$."},{"iden":"sample input 3","content":"10000000000 10 99959"},{"iden":"sample output 3","content":"492443256176507"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}