Cerința

Se dă n un număr natural. Într-un şir de lungime n, format cu cifrele 0 şi 1, numim insulă o secvenţă maximă de cifre egale. Să se afle câte insule se află în toate şirurile de lungime n, formate cu cifrele 0 şi 1.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran numărul insulelor care se află în toate şirurile de lungime n, formate cu cifrele 0 şi 1. Deoarece acest număr este prea mare, se va afişa modulo 1.000.000.007.

Restricții și precizări

• 1 ≤ n ≤ 1.000.000.000

Exemplu:

Intrare

2

Ieșire

6

Explicație

Şirurile de lungime 2 formate cu cifrele 0 şi 1 sunt 00, 01, 10, 11, acestea conţinând 1, 2, 2, respectiv 1 insule. În total sunt 6 insule.