Statement

A positive integer is called excellent if its decimal representation contains only the digits 1 and 5, and it is divisible by 3. For example, 15 and 111 are excellent numbers (15 = 5* 3 + 0 and 111=37* 3 + 0), while 151 is not (151 = 50* 3 + 1). \footnotetextThe hex triplet is a way to represent colors as its Red, Green, and Blue components with two hex digits (one byte) for each component. Alex observed that there are many excellent numbers formed by N digits, and thus he started counting them. However, this is taking too much time, so he gave this task as a homework for you: help him count how many excellent numbers of N digits exist! Since the answer can be big, print it modulo 10^9 + 7.