Şimal-şərq kralı

Sol aşağı küncdə yerləşən $n\times n$ ölçülü kvadrat şahmat taxtasında bir şah var. Şah yalnız bir xanaya sağa, yuxarıya və ya diaqonal olaraq sağa yuxarıya hərəkət edə bilər. Şahın taxtanın sağ üst küncünə neçə fərqli üsulla çata biləcəyini $1000003$ modulu ilə hesablayın.

Giriş verilənləri

Birinci sətir testlərin sayını göstərir $t(1\le t\le 1000)$. Sonrakı $t$ sətirin hər biri bir tam ədəd $n(1\le n\le 1000)$ ehtiva edir.

Çıxış verilənləri

Hər bir $n$ dəyəri üçün mümkün olan üsulların sayını çıxarın.

Nümunələr