Tehtäväsi on laskea, montako eri tapaa on saada summa n noppaa heittämällä. Jokainen nopan heitto tuottaa luvun väliltä 1 \ldots 6.

Esimerkiksi jos n=10, esimerkkejä tavoista ovat 3+3+4, 1+4+1+4 ja 1+1+6+1+1.

Syöte

Syötteenä on tavoitteena oleva luku n.

Tuloste

Tulosta tapojen määrä modulo 10^9+7.

Rajat

• 1 \le n \le 10^{18}

Esimerkki

Syöte:

8

Tuloste:

125