Командanın cəbr işi
Zəngin qrup nəzəriyyəsi və xətti cəbrin məşhur pionerləri öz nəzəriyyələrini birləşdirmək və əməkdaşlıq etmək istəyirlər. Qrup nəzəriyyəsində dəyişmələr – həmçinin biyektiv funksiyalar kimi tanınır – mühüm rol oynayır. Sonlu A çoxluğu üçün, σ : A → A funksiyası A-nın dəyişməsi adlanır əgər belə bir ρ : A → A funksiyası mövcuddursa ki,
σ(ρ(a)) = a və ρ(σ(a)) = a hər bir a üçün A-dan.
Yeni komandanın ikinci hissəsi - xətti cəbr üzrə mütəxəssislər - idempotent funksiyalarla məşğul olurlar. Onlar 3D oyunlarda kölgələrin hesablanmasında və ya məsələn tranzitiv bağlanmaların hesablanmasında meydana çıxır. p : A → A funksiyası yalnız o zaman idempotent adlanır ki,
p(p(a)) = p(a) hər bir a üçün A-dan.
Araşdırmanı davam etdirmək üçün onların sizin köməyinizə ehtiyacı var. Komanda verilmiş sonlu çoxluq A üçün qeyri-idempotent dəyişmələrlə maraqlanır. Əvvəlcə onlar aşkar etdilər ki, nəticə çoxluğun ölçüsündən asılıdır. Verilmiş n ölçüsü üçün (1 ≤ n ≤ 10^5) n ölçüsündə çoxluq üçün qeyri-idempotent dəyişmələrin sayını tapmalısınız.
Giriş məlumatları
Testlərin sayı t (t ≤ 100) ilə başlayır. Sonra t sətir gəlir, hər biri çoxluğun ölçüsü n (1 ≤ n ≤ 10^5) ilə.
Çıxış məlumatları
Hər bir test üçün ayrıca sətirdə n gücündə qeyri-idempotent funksiyaların sayını 1 000 000 007 = (10^9 + 7) moduluna görə çıxarın.