НОD müəyyənedicisi

Müəyyən edək ki, S = {x_1, x_2, ..., x_n} çoxluğu faktor-bağlıdır, əgər hər hansı x_i ∈ S və onun hər hansı böləninin böləni d üçün d ∈ S şərti ödənilirsə. GCD matrisi (S) = (s_ij) quracağıq, burada s_ij = GCD(x_i, x_j) - x_i və x_j-nin ən böyük ortaq bölənidir. Bilərək ki, S çoxluğu faktor-bağlıdır, determinantın dəyərini hesablayın:

Giriş verilənləri

Bir neçə testdən ibarətdir. Hər bir test n (0 < n < 1000) tam ədədi ilə başlayır, bu da S çoxluğunun gücünə bərabərdir. Növbəti sətir S çoxluğunun ədədlərini ehtiva edir: x_1, x_2, ..., x_n. Hər bir x_i tam ədəd olduğu məlumdur, 0 ≤ x_i ≤ 2·10^9. Giriş məlumatları düzgündür və faylın sonu simvolu ilə bitir.

Çıxış verilənləri

Hər bir test üçün ayrıca sətirdə D_n mod 1000000007 dəyərini çıxarın.

Nümunələr