НСД-təyin edici#3243
Vasya yaxınlarda determinantları öyrəndi və indi onları ədədlər nəzəriyyəsi sahəsində tətbiq etmək istəyir. O, n×n ölçülü bir matrisa tərtib etdi, burada i-ci sırada j mövqeyində ƏBOB(i, j) sayı yerləşir. Məsələn, n = 3 olduqda aşağıdakı determinantı alırıq:
İndi Vasya bu matrisanın determinantının dəyərini hesablamaq istəyir, lakin bu məsələ onun üçün çətin oldu və indi siz onu həll etməlisiniz. Determinant kifayət qədər böyük ola biləcəyi üçün Vasya onun 500009 modulu ilə hesablanmasını xahiş edir.
Giriş faylının ilk sətrində testlərin sayı t (1 ≤ t ≤ 100000) verilir. Hər bir növbəti sətir determinantın nizamını göstərən n ədədini (1 ≤ n ≤ 10^9) ehtiva edir.
Hər bir test üçün müvafiq determinantın 500009 modulu ilə dəyərini çıxarın.
Nümunə 1