No tags yet

No tag edit access

The problem statement has recently been changed. View the changes.

×
time limit per test: 1.75 sec.

memory limit per test: 65536 KB

memory limit per test: 65536 KB

input: standard

output: standard

output: standard

He wrote n letters "X" and "E" in a circle. He thought that there were 2n possibilities to do it, because each letter may be either "X" or "E". 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).

For example, strings "XXE"-"XEX"-"EXX" are actually the same.

Qc wants to know how many different circular strings of n letters exist. Help him to find that out.

For example, strings "XXE"-"XEX"-"EXX" are actually the same.

Qc wants to know how many different circular strings of n letters exist. Help him to find that out.

The input file contains a single integer 1 <= n <= 200000.

Output a single integer --- the number circular strings of length n.

Input

Test #1

3

Test #2

4

3

Test #2

4

Output

Test #1

4

Test #2

6

4

Test #2

6

Author: | Anton Golubev, Petrazavodsk SU |

Resource: | Anton Golubev (Hedgehog)'s Contest #2 from Annual Summer Russian Teams Meeting in Petrozavodsk State University |

Date: | August 26, 2005 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/14/2021 05:02:14 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|