Algorithms and Data Structures

• Status
• 1
Implementation
• 2
Bitwise operations
• 3
Prefix Sums
• 4
Sliding window / Two pointers
• 5
Modular Arithmetic
• 6
Number Theory
• 7
Binary Search
• 8
Basic Sorting
• 9
Greedy Algorithms
• 10
Basic Dynamic Programming
• 11
Recursion
• 12
• 13
Queue & Stack
• 14
Binary tree + BST
• 15
Divide & Conquer + Advanced Sorting
• 16
Heap
• 17
Hashing
• 18
Graph Representation
• 19
BFS

• # Number of bit-strings

Given an integer `n`, you are asked to calculate the number of different bit-strings of length `n`. As the resulting number might be too big, the output should contain the number of bit-strings modulo (1000000007).

#### Input

The input contains a single integer `n` (1 ≤ n ≤ ).

#### Output

The program should print the number of bit-strings of length `n` modulo .

#### Examples

 Input Output 3 8 2 4

#### Explanation

1. 3: 000, 001, 010, 011, 100, 101, 110, 111
1. 2: 00, 01, 10, 11

#### Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB