Lanterns#5081
Night lighting needs to be installed on the road. A working team has already installed lanterns, and now they just need to be turned on. To save money, it was decided to turn on a sufficient number of lanterns to ensure the road is safe to drive on. The road is considered safe only if there are no segments of the road with consecutive lanterns turned off.
Determine the number of ways to turn on the lanterns so that the road remains safe for driving. Two lighting configurations are considered different if there is at least one lantern that is on in one configuration and off in the other. Since the number of such configurations can be very large, print the result modulo 10^9 + 7.
Two integers n~(1 \le n \le 10^6) and k~(1 \le k \le n).
Print the number of ways to turn on the lanterns that ensure safe driving on the road.
Example 1