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
Output format
Print an integer denoting the number of ways to color the remaining bricks modulo .
Constraints
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,