Color the bricks

4

11 votes
2-D Array, Algorithms, Dynamic Programming, Easy
Problem

You are given bricks that are numbered from to . You are required to color all the bricks. Here, bricks are already colored.

You can only color the  brick if the  or  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 .
Input format

  • First line: Two space-separated integer
  • Second line: 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 .

Constraints

Sample Input
6 3
1 2 6
Sample Output
4
Time Limit: 1
Memory Limit: 256
Source Limit:
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,

Editor Image

?