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...

## This Problem was Asked in Challenge Name

August Easy' 19

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Input/Output
• Math > Basic Math
• Data Structures > Advanced Data Structures
• Math > Basic Math
• Data Structures > Advanced Data Structures
Уведомления

?