All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Color the bricks
Tag(s):

2 Dimensional, Algorithms, Dynamic Programming, Easy-Medium

Problem
Editorial
Analytics

You are given \(N\) bricks that are numbered from \(1\) to \(N\). You are required to color all the bricks. Here, \(K\) bricks are already colored.

You can only color the \(i^{th}\) brick if the \((i+1)^{th}\) or \((i-1)^{th}\) brick is already colored. Your task is to determine the number of ways you can color all the remaining bricks. Since the number of ways can be very large, therefore print the number of ways modulo \(1000000007\).
Input format

  • First line: Two space-separated integer \(N,\ K\)
  • Second line: \(K\) space-separated integers each denoting the brick that is already colored

Output format

Print an integer denoting the number of ways to color the remaining bricks modulo \(1000000007\).

Constraints

\(1\le K\le N\le1000\)

SAMPLE INPUT
6 3
1 2 6
SAMPLE OUTPUT
4
Explanation

Bob can paint the remaining bricks in following way - {3,4,5},{3,5,4},{5,3,4},{5,4,3}. So total 4 ways possible,

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

August Easy' 19

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?