НСД-təyin edici

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ş verilənləri

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.

Çıxış verilənləri

Hər bir test üçün müvafiq determinantın 500009 modulu ilə dəyərini çıxarın.

Nümunələr