Heç vaxt çox içmə!
Mahmud dostları ilə birlikdə Gürcüstana səfər etdi. Onlar Rustavelli küçəsindəki bir oteldə qalacaqdılar. Kovboylar otelə çatanda, girişdə şlyapalarını asıb yerləşdilər. Mahmud dəhlizdən keçərkən masadakı pivə butulkaları onun diqqətindən qaçmadı. Mahmudun təklifi ilə bütün kovboylar içməyə başladılar. Çox içdilər, buna görə də heç biri özünü idarə edə bilmədi. Sonra şəhərin mərkəzinə getməyə qərar verdilər. Çıxarkən hər kəsin başında bir şlyapa vardı, amma sərxoş olduqları üçün şlyapaları qarışdırdılar.
Sərxoş halda öz şlyapasını geyinə bilən adam ağıllı, bunu bacarmayan isə axmaq sayılır.
Sizə kovboyların sayı - n (Mahmud daxil olmaqla) verilir. Kovboyların hamısının axmaq olduğu halda şlyapaları neçə cür geyinə biləcəyini tapmalısınız. İki yol fərqli sayılır, əgər ən azı bir kovboy bir halda bir şlyapa, digər halda isə başqa bir şlyapa geyinibsə.
Cavab çox böyük ola biləcəyi üçün nəticəni 10^9 + 7 modulu ilə çıxış etməlisiniz.
Giriş
Kovboyların sayı verilir - n (1 ≤ n ≤ 10^7).
Çıxış
Yuxarıda göstərilən problemə cavab.