{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tHe wrote n letters \u0026quot;X\u0026quot; and \u0026quot;E\u0026quot; in a circle. He thought that there were 2n possibilities to do it, because each letter may be either \u0026quot;X\u0026quot; or \u0026quot;E\u0026quot;. But Qc noticed that some different sequences of letters can be transformed one to another with a circular shift (thus representing actually the same circular string).\u0026nbsp;\u003c/p\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\tFor example, strings \u0026quot;XXE\u0026quot;-\u0026quot;XEX\u0026quot;-\u0026quot;EXX\u0026quot; are actually the same.\u0026nbsp;\u003cbr /\u003e\r\n\tQc wants to know how many different circular strings of n letters exist. Help him to find that out.\u0026nbsp;\u003cbr /\u003e\r\n\t\u003ccenter\u003e\r\n\t\t\u003cimg src\u003d\"http://acm.sgu.ru/images/ph-15.gif\" /\u003e\u003c/center\u003e\r\n\u003c/div\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\t\u003cbr /\u003e\r\n\t\u003cb\u003eInput\u003c/b\u003e\u003c/div\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\tThe input file contains a single integer 1 \u0026lt;\u003d n \u0026lt;\u003d 200000.\u003c/div\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\t\u003cbr /\u003e\r\n\t\u003cb\u003eOutput\u003c/b\u003e\u003c/div\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\tOutput a single integer --- the number circular strings of length n.\u0026nbsp;\u003c/div\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\t\u003cbr /\u003e\r\n\t\u003cb\u003eSample test(s)\u003c/b\u003e\u003c/div\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\t\u003cbr /\u003e\r\n\tInput\u003c/div\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\t\u0026nbsp;\u003c/div\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\t\u003cpre\u003e\u003c/pre\u003e\r\n\u003c/div\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\t\u003cfont face\u003d\"Courier New\"\u003eTest #1\u0026nbsp;\u003cbr /\u003e\r\n\t3\u0026nbsp;\u003cbr /\u003e\r\n\t\u003cbr /\u003e\r\n\tTest #2\u0026nbsp;\u003cbr /\u003e\r\n\t4\u0026nbsp;\u003c/font\u003e\u003c/div\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\t\u0026nbsp;\u003c/div\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\t\u0026nbsp;\u003c/div\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\t\u003cbr /\u003e\r\n\tOutput\u003c/div\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\t\u0026nbsp;\u003c/div\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\t\u003cpre\u003e\u003c/pre\u003e\r\n\u003c/div\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\t\u003cfont face\u003d\"Courier New\"\u003eTest #1\u0026nbsp;\u003cbr /\u003e\r\n\t4\u0026nbsp;\u003cbr /\u003e\r\n\t\u003cbr /\u003e\r\n\tTest #2\u0026nbsp;\u003cbr /\u003e\r\n\t6\u003c/font\u003e\u003c/div\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\t\u0026nbsp;\u003c/div\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\t\u0026nbsp;\u003c/div\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\t\u003cdiv align\u003d\"right\"\u003e\r\n\t\t\u003ca href\u003d\"http://acm.sgu.ru/submit.php?problem\u003d294\" style\u003d\"color: rgb(34, 68, 136); text-decoration: none; \"\u003e[submit]\u003c/a\u003e\u003c/div\u003e\r\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv align\u003d\"left\"\u003e\r\n\tThe input file contains a single integer 1 \u0026lt;\u003d n \u0026lt;\u003d 200000.\u003c/div\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e\r\n\t环可以旋转,不可以翻转。\u003c/p\u003e"}}]}