Командanın cəbr işi#7695

Командanın cəbr işi

1 saniyə

128 meqabayt

Orta

Qrup nəzəriyyəsi və xətti cəbrin böyük pionerləri birgə işləyərək nəzəriyyələrini birləşdirmə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 \to A$ \sigma : A \rightarrow A funksiyası yalnız o halda $A$ -nın dəyişməsi adlanır ki, elə bir $ρ : A \to A$ \rho : A \rightarrow A funksiyası mövcuddur və

σ (ρ (a)) = a və ρ (σ (a)) = a hər bir a \in A

\sigma(\rho(a)) = a \text{ və } \rho(\sigma(a)) = a \text{ hər bir } a \in A

Komandanın digər hissəsi — xətti cəbr üzrə mütəxəssislər — idempotent funksiyalarla məşğul olurlar. Belə funksiyalar, məsələn, 3D oyunlarda kölgələrin hesablanmasında və ya tranzitiv bağlamanın tapılmasında meydana çıxır. $p : A \to A$ p : A \rightarrow A funksiyası yalnız o halda idempotent adlanır ki,

p (p (a)) = p (a) hər bir a \in A

p(p(a)) = p(a) \text{ hər bir } a \in A

Araşdırmanı davam etdirmək üçün onlara sizin köməyiniz lazımdır. Komanda verilmiş sonlu çoxluq $A$ üçün qeyri-idempotent dəyişmələrlə maraqlanır. Əvvəlcə onlar müəyyən etdilər ki, nəticə çoxluğun ölçüsündən asılıdır. Verilmiş $n$ ölçüsündə ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5) çoxluq üçün qeyri-idempotent dəyişmələrin sayını tapmalısınız.

\InputFileGiriş sətiri testlərin sayı olan bir tam ədəd $t$ ( $1 \leq t \leq 100$ 1 \leq t \leq 100) ilə başlayır. Sonra $t$ sətir gəlir, hər biri çoxluğun ölçüsünü bildirən bir tam ədəd $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5).

\OutputFileHər test üçün $n$ gücündə qeyri-idempotent dəyişmələrin sayını $1000000007$ $= 1 0^{9} + 7$ = 10^9 + 7 moduluna görə ayrıca sətirdə çıxarın.

Nümunələr

Nümunə 1

Loading

σ : A \to A

ρ : A \to A

σ (ρ (a)) = a və ρ (σ (a)) = a hər bir a \in A

p : A \to A

p (p (a)) = p (a) hər bir a \in A

1 \leq n \leq 1 0^{5}

1 \leq t \leq 100

1 \leq n \leq 1 0^{5}

= 1 0^{9} + 7