Submit solution

Points:
15 (partial)

Time limit:
0.6s

Memory limit:
162M

Problem types

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, ~~CommonLisp~~, D, Dart, F#, Forth, Fortran, Go, ~~Groovy~~, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ~~Nim~~, ~~ObjC~~, OCaml, ~~Octave~~, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

A circle is drawn with center at and points through are equally spaced around the circle.

Line segments are drawn to connect to each of these points.

Compute the number of ways to delete of the line segments or arcs such that the points are still connected.

#### Constraints

In test data worth 10% of marks, you may assume .

#### Input Specification

The first and only line contains a single positive integer, .

#### Output Specification

Output the number of desired configurations.

#### Sample Input

`3`

#### Sample Output

`16`

## Comments