Ящикlər və toplar

Rəngləri fərqli olan $n$ qutu var. Hər rəngdən məhdudiyyətsiz sayda top mövcuddur. Hər bir qutuya bir top yerləşdirin ki, qonşu qutularda eyni rəngdə top olmasın. Qutulara topların neçə fərqli şəkildə yerləşdirilə biləcəyini tapın.

Giriş verilənləri

Bir tam ədəd $n(1\le n\le 10^9)$.

Çıxış verilənləri

Qutulara topların fərqli yerləşdirilmə sayını $10^9+7$ modulu ilə hesablayıb çıxarın.

Nümunələr