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

  • Filling the array

    Given an array of n elements, you know that all the values in the array are between 1 and m. Besides that, the absolute difference between two adjacent elements is at most 1. Some of the values have been erased from the array and you’re asked to calculate the number of different ways the array can be filled without breaking the conditions.

    Input

    The first line of the input contains two integers n (1 ≤ n ≤ ) and m (1 ≤ m ≤ 100).
    The next line contains n space-separated integers (1 ≤ ≤ m) representing the elements in the array. The value of being 0 denotes the erased value at position i.

    Output

    The program should print the number of ways to fill the array that satisfy the conditions. The output can be large, so the answer should be taken modulo .

    Examples

    Input
    Output
    3 5 2 0 2
    3

    Explanation

    1. 2 1 2
    1. 2 2 2
    1. 2 3 2
     

    Constraints

    Time limit: 3 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

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