Algorithms and Data Structures

  • Profound Academy

    • 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
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • Paint with colors

    You’d like to paint a stripe with 3 colors - red, blue, and orange. You paint each unit with one color. To make it more eye-catching, you’ve decided to follow these rules:
    1. You cannot place the same colors next to each other
    1. The blue color should always be placed between the red and the orange or the orange and the red.
    How many different stripes can you obtain if there are n units in the whole stripe?

    Input

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

    Output

    The program should print the number of different stripes you can obtain. As the answer can be large, you are asked to print the answer modulo .

    Examples

    Input
    Output
    1
    2
    2
    2
    3
    4

    Explanation

    1. (red) (orange)
    1. (red, orange) (orange, red)
    1. (orange, red, orange) (red, blue, orange) (orange, blue, red) (red, orange, red)
     

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue