Balanced String

Time limit0.5sMemory limit512 MB

Summary

Count binary strings of length n where every prefix has at most one more 0 than 1 or one more 1 than 0, modulo 16769023.

Level: Medium6 of 10
Topics: Dynamic programming, Combinatorics, Math, String
Solved: No attempts yet

Problem

The binary string 0101101, made of 0s and 1s, has a difference of at most 1 between the numbers of 0s and 1s. Its every prefix, meaning every substring that contains the first character: 0, 01, 010, 0101, 01011, 010110, 0101101, also has a difference of at most 1 between the numbers of 0s and 1s.

A binary string is called a balanced string when every substring that contains its first character has a difference of at most 1 between the numbers of 0s and 1s. A string is a substring of itself.

Given a positive integer n, write a program that finds the number of balanced strings among the binary strings of length n.

For example, when n = 3, the four strings 010, 011, 100, 101 are balanced.

Input

Input is read from standard input. The first line contains a positive integer n (1 ≤ n ≤ 100,000).

Output

Output is written to standard output. Print the number of balanced strings among the binary strings of length n, modulo 16769023, on a single line.

Examples3

Example 1
Input
```
3
```
Expected output
```
4
```
Example 2
Input
```
22
```
Expected output
```
2048
```
Example 3
Input
```
101
```
Expected output
```
393256
```