Problem :
You are given N numbers from 1 to N. Your friend asked you to give him an array of size M that is made of numbers from 1 to N. Each of the numbers from 1 to N have a type 1, 2, 3 or 4. Your friend has a switch that controls a light bulb. You are given that initially, the light bulb is on.
When you give your friend the array, he will start reading the numbers from left to right in the array, and one of the following things will happen:
• If the number is of type 1, then he will flip the switch, i.e if the light bulb is on then it will become off and if it was off then it will become on.
• If the number is of type 2, then he will switch the light bulb on irrespective of whether it was on or off.
• If the number is of type 3, then he will switch the light bulb off irrespective of whether it was on or off.
• If the number is of type 4, then he will do nothing.
Your task is to calculate the number of ways in which you can create an array such that in the end the light bulb is on. Since the answer could be very large, return it to modulo 10^9+7.
N<1e5
M<1e9
Sample :
5
6
1 1 1 1 1
Output : 15625
Explanation : 5^6.
My approach : I wrote O(m) dp approach which will obviously timeout.
Can anyone explain the correct way of approaching it ? 
Note : This problem was asked in 7th may 3PM slot. Contest is already over.