import java.io.EOFException;
import java.io.File;
import java.io.FileDescriptor;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.UncheckedIOException;
import java.lang.reflect.Field;
import java.nio.CharBuffer;
import java.nio.charset.CharacterCodingException;
import java.nio.charset.CharsetEncoder;
import java.nio.charset.StandardCharsets;
import java.util.Arrays;
import java.util.OptionalLong;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;



public class Main {
    public static void main(String[] args) throws Exception {
        ExtendedScanner sc = new ExtendedScanner();
        FastPrintStream pw = new FastPrintStream();
        solve(sc, pw);
        sc.close();
        pw.flush();
        pw.close();
    }

    static final class ModArithmetic1000000009 extends ModArithmetic {
        public static final ModArithmetic INSTANCE = new ModArithmetic1000000009();
        private ModArithmetic1000000009(){}
        public static final long MOD = 1000000009;
        public long getMod() {return MOD;}
        public long mod(long a) {return (a %= MOD) < 0 ? a + MOD : a;}
        public long add(long a, long b) {return (a += b) >= MOD ? a - MOD : a;}
        public long sub(long a, long b) {return (a -= b) < 0 ? a + MOD : a;}
        public long mul(long a, long b) {return (a * b) % MOD;}
    }

    static final ModArithmetic ma = ModArithmetic1000000009.INSTANCE;
    static final int MAX = 100000;

    public static void solve(ExtendedScanner sc, FastPrintStream pw) {
        long[] f = new long[MAX + 1];
        Arrays.fill(f, 1);
        for (int i = 1; i <= 9; i++) {
            for (int j = i; j <= MAX; j++) {
                f[j] = ma.add(f[j], f[j - i]);
            }
        }

        int t = sc.nextInt();
        while (t --> 0) {
            int m = (int) (sc.nextLong() / 111111);
            pw.println(f[m]);
        }
    }
}


/**
 * @author https://atcoder.jp/users/suisen
 */
final class ExtendedScanner extends FastScanner {
    public ExtendedScanner() {super();}
    public ExtendedScanner(InputStream in) {super(in);}
    public int[] ints(final int n) {
        final int[] a = new int[n];
        Arrays.setAll(a, $ -> nextInt());
        return a;
    }
    public int[] ints(final int n, final IntUnaryOperator f) {
        final int[] a = new int[n];
        Arrays.setAll(a, $ -> f.applyAsInt(nextInt()));
        return a;
    }
    public int[][] ints(final int n, final int m) {
        final int[][] a = new int[n][];
        Arrays.setAll(a, $ -> ints(m));
        return a;
    }
    public int[][] ints(final int n, final int m, final IntUnaryOperator f) {
        final int[][] a = new int[n][];
        Arrays.setAll(a, $ -> ints(m, f));
        return a;
    }
    public long[] longs(final int n) {
        final long[] a = new long[n];
        Arrays.setAll(a, $ -> nextLong());
        return a;
    }
    public long[] longs(final int n, final LongUnaryOperator f) {
        final long[] a = new long[n];
        Arrays.setAll(a, $ -> f.applyAsLong(nextLong()));
        return a;
    }
    public long[][] longs(final int n, final int m) {
        final long[][] a = new long[n][];
        Arrays.setAll(a, $ -> longs(m));
        return a;
    }
    public long[][] longs(final int n, final int m, final LongUnaryOperator f) {
        final long[][] a = new long[n][];
        Arrays.setAll(a, $ -> longs(m, f));
        return a;
    }
    public char[][] charArrays(final int n) {
        final char[][] c = new char[n][];
        Arrays.setAll(c, $ -> nextChars());
        return c;
    }
    public double[] doubles(final int n) {
        final double[] a = new double[n];
        Arrays.setAll(a, $ -> nextDouble());
        return a;
    }
    public double[][] doubles(final int n, final int m) {
        final double[][] a = new double[n][];
        Arrays.setAll(a, $ -> doubles(m));
        return a;
    }
    public String[] strings(final int n) {
        final String[] s = new String[n];
        Arrays.setAll(s, $ -> next());
        return s;
    }
}

/**
 * @author https://atcoder.jp/users/suisen
 */
class FastPrintStream implements AutoCloseable {
    private static final int INT_MAX_LEN = 11;
    private static final int LONG_MAX_LEN = 20;

    private int precision = 9;

    private static final int BUF_SIZE = 1 << 14;
    private static final int BUF_SIZE_MINUS_INT_MAX_LEN = BUF_SIZE - INT_MAX_LEN;
    private static final int BUF_SIZE_MINUS_LONG_MAX_LEN = BUF_SIZE - LONG_MAX_LEN;
    private final byte[] buf = new byte[BUF_SIZE];
    private int ptr = 0;
    private final Field strField;
    private final CharsetEncoder encoder;

    private final OutputStream out;

    public FastPrintStream(OutputStream out) {
        this.out = out;
        Field f;
        try {
            f = String.class.getDeclaredField("value");
            f.setAccessible(true);
        } catch (NoSuchFieldException | SecurityException e) {
            f = null;
        }
        this.strField = f;
        this.encoder = StandardCharsets.US_ASCII.newEncoder();
    }

    public FastPrintStream(File file) throws IOException {
        this(new FileOutputStream(file));
    }

    public FastPrintStream(String filename) throws IOException {
        this(new File(filename));
    }

    public FastPrintStream() {
        this(new FileOutputStream(FileDescriptor.out));
    }

    public FastPrintStream println() {
        if (ptr == BUF_SIZE) internalFlush();
        buf[ptr++] = (byte) '\n';
        return this;
    }

    public FastPrintStream println(Object o) {
        return print(o).println();
    }

    public FastPrintStream println(String s) {
        return print(s).println();
    }

    public FastPrintStream println(char[] s) {
        return print(s).println();
    }

    public FastPrintStream println(char c) {
        return print(c).println();
    }

    public FastPrintStream println(int x) {
        return print(x).println();
    }

    public FastPrintStream println(long x) {
        return print(x).println();
    }

    public FastPrintStream println(double d, int precision) {
        return print(d, precision).println();
    }

    public FastPrintStream println(double d) {
        return print(d).println();
    }

    private FastPrintStream print(byte[] bytes) {
        int n = bytes.length;
        if (ptr + n > BUF_SIZE) {
            internalFlush();
            try {
                out.write(bytes);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        } else {
            System.arraycopy(bytes, 0, buf, ptr, n);
            ptr += n;
        }
        return this;
    }

    public FastPrintStream print(Object o) {
        return print(o.toString());
    }

    public FastPrintStream print(String s) {
        if (strField == null) {
            return print(s.getBytes());
        } else {
            try {
                Object value = strField.get(s);
                if (value instanceof byte[]) {
                    return print((byte[]) value);
                } else {
                    return print((char[]) value);
                }
            } catch (IllegalAccessException e) {
                return print(s.getBytes());
            }
        }
    }

    public FastPrintStream print(char[] s) {
        try {
            return print(encoder.encode(CharBuffer.wrap(s)).array());
        } catch (CharacterCodingException e) {
            byte[] bytes = new byte[s.length];
            for (int i = 0; i < s.length; i++) {
                bytes[i] = (byte) s[i];
            }
            return print(bytes);
        }
    }

    public FastPrintStream print(char c) {
        if (ptr == BUF_SIZE) internalFlush();
        buf[ptr++] = (byte) c;
        return this;
    }

    public FastPrintStream print(int x) {
        if (ptr > BUF_SIZE_MINUS_INT_MAX_LEN) internalFlush();
        if (-10 < x && x < 10) {
            if (x < 0) {
                buf[ptr++] = '-';
                x = -x;
            }
            buf[ptr++] = (byte) ('0' + x);
            return this;
        }
        int d;
        if (x < 0) {
            if (x == Integer.MIN_VALUE) {
                buf[ptr++] = '-'; buf[ptr++] = '2'; buf[ptr++] = '1'; buf[ptr++] = '4';
                buf[ptr++] = '7'; buf[ptr++] = '4'; buf[ptr++] = '8'; buf[ptr++] = '3';
                buf[ptr++] = '6'; buf[ptr++] = '4'; buf[ptr++] = '8';
                return this;
            }
            d = len(x = -x);
            buf[ptr++] = '-';
        } else {
            d = len(x);
        }
        int j = ptr += d; 
        while (x > 0) {
            buf[--j] = (byte) ('0' + (x % 10));
            x /= 10;
        }
        return this;
    }

    public FastPrintStream print(long x) {
        if ((int) x == x) return print((int) x);
        if (ptr > BUF_SIZE_MINUS_LONG_MAX_LEN) internalFlush();
        int d;
        if (x < 0) {
            if (x == Long.MIN_VALUE) {
                buf[ptr++] = '-'; buf[ptr++] = '9'; buf[ptr++] = '2'; buf[ptr++] = '2';
                buf[ptr++] = '3'; buf[ptr++] = '3'; buf[ptr++] = '7'; buf[ptr++] = '2';
                buf[ptr++] = '0'; buf[ptr++] = '3'; buf[ptr++] = '6'; buf[ptr++] = '8';
                buf[ptr++] = '5'; buf[ptr++] = '4'; buf[ptr++] = '7'; buf[ptr++] = '7';
                buf[ptr++] = '5'; buf[ptr++] = '8'; buf[ptr++] = '0'; buf[ptr++] = '8';
                return this;
            }
            d = len(x = -x);
            buf[ptr++] = '-';
        } else {
            d = len(x);
        }
        int j = ptr += d; 
        while (x > 0) {
            buf[--j] = (byte) ('0' + (x % 10));
            x /= 10;
        }
        return this;
    }

    public FastPrintStream print(double d, int precision) {
        if (d < 0) {
            print('-');
            d = -d;
        }
        d += Math.pow(10, -precision) / 2;
        print((long) d).print('.');
        d -= (long) d;
        for(int i = 0; i < precision; i++){
            d *= 10;
            print((int) d);
            d -= (int) d;
        }
        return this;
    }

    public FastPrintStream print(double d) {
        return print(d, precision);
    }

    public void setPrecision(int precision) {
        this.precision = precision;
    }

    private void internalFlush() {
        try {
            out.write(buf, 0, ptr);
            ptr = 0;
        } catch (IOException e) {
            throw new UncheckedIOException(e);
        }
    }

    public void flush() {
        try {
            out.write(buf, 0, ptr);
            out.flush();
            ptr = 0;
        } catch (IOException e) {
            throw new UncheckedIOException(e);
        }
    }

    public void close() {
        try {
            out.close();
        } catch (IOException e) {
            throw new UncheckedIOException(e);
        }
    }

    private static int len(int x) {
        return
            x >= 1000000000 ? 10 :
            x >= 100000000  ?  9 :
            x >= 10000000   ?  8 :
            x >= 1000000    ?  7 :
            x >= 100000     ?  6 :
            x >= 10000      ?  5 :
            x >= 1000       ?  4 :
            x >= 100        ?  3 :
            x >= 10         ?  2 : 1;
    }

    private static int len(long x) {
        return
            x >= 1000000000000000000L ? 19 :
            x >= 100000000000000000L ? 18 :
            x >= 10000000000000000L ? 17 :
            x >= 1000000000000000L ? 16 :
            x >= 100000000000000L ? 15 :
            x >= 10000000000000L ? 14 :
            x >= 1000000000000L ? 13 :
            x >= 100000000000L ? 12 :
            x >= 10000000000L ? 11 : 10;
    }
}

/**
 * @author https://atcoder.jp/users/suisen
 */
class FastScanner implements AutoCloseable {
    private final ByteBuffer tokenBuf = new ByteBuffer();
    public final InputStream in;
    private final byte[] rawBuf = new byte[1 << 14];
    private int ptr = 0;
    private int buflen = 0;

    public FastScanner(InputStream in) {
        this.in = in;
    }

    public FastScanner() {
        this(new FileInputStream(FileDescriptor.in));
    }

    private int readByte() {
        if (ptr < buflen) return rawBuf[ptr++];
        ptr = 0;
        try {
            buflen = in.read(rawBuf);
            if (buflen > 0) {
                return rawBuf[ptr++];
            } else {
                throw new EOFException();
            }
        } catch (IOException e) {
            throw new UncheckedIOException(e);
        }
    }

    private int readByteUnsafe() {
        if (ptr < buflen) return rawBuf[ptr++];
        ptr = 0;
        try {
            buflen = in.read(rawBuf);
            if (buflen > 0) {
                return rawBuf[ptr++];
            } else {
                return -1;
            }
        } catch (IOException e) {
            throw new UncheckedIOException(e);
        }
    }

    private int skipUnprintableChars() {
        int b = readByte();
        while (b <= 32 || b >= 127) b = readByte();
        return b;
    }

    private void loadToken() {
        tokenBuf.clear();
        for (int b = skipUnprintableChars(); 32 < b && b < 127; b = readByteUnsafe()) {
            tokenBuf.append(b);
        }
    }

    public final boolean hasNext() {
        for (int b = readByteUnsafe(); b <= 32 || b >= 127; b = readByteUnsafe()) {
            if (b == -1) return false;
        }
        --ptr;
        return true;
    }

    public final String next() {
        loadToken();
        return new String(tokenBuf.getRawBuf(), 0, tokenBuf.size());
    }

    public final String nextLine() {
        tokenBuf.clear();
        for (int b = readByte(); b != '\n'; b = readByteUnsafe()) {
            if (b == -1) break;
            tokenBuf.append(b);
        }
        return new String(tokenBuf.getRawBuf(), 0, tokenBuf.size());
    }

    public final char nextChar() {
        return (char) skipUnprintableChars();
    }

    public final char[] nextChars() {
        loadToken();
        return tokenBuf.toCharArray();
    }

    public final long nextLong() {
        long n = 0;
        boolean isNegative = false;
        int b = skipUnprintableChars();
        if (b == '-') {
            isNegative = true;
            b = readByteUnsafe();
        }
        if (b < '0' || '9' < b) throw new NumberFormatException();
        while ('0' <= b && b <= '9') {
            // -9223372036854775808 - 9223372036854775807
            if (n >= 922337203685477580L) {
                if (n > 922337203685477580L) {
                    throw new ArithmeticException("long overflow");
                }
                if (isNegative) {
                    if (b >= '9') {
                        throw new ArithmeticException("long overflow");
                    }
                    n = -n - (b - '0');
                } else {
                    if (b >= '8') {
                        throw new ArithmeticException("long overflow");
                    }
                    n = n * 10 + b - '0';
                }
                b = readByteUnsafe();
                if ('0' <= b && b <= '9') {
                    throw new ArithmeticException("long overflow");
                } else if (b <= 32 || b >= 127) {
                    return n;
                } else {
                    throw new NumberFormatException();
                }
            }
            n = n * 10 + b - '0';
            b = readByteUnsafe();
        }
        if (b <= 32 || b >= 127) return isNegative ? -n : n;
        throw new NumberFormatException();
    }
    public final int nextInt() {
        long value = nextLong();
        if ((int) value != value) {
            throw new ArithmeticException("int overflow");
        }
        return (int) value;
    }
    public final double nextDouble() {
        return Double.parseDouble(next());
    }
    public final void close() {
        try {
            in.close();
        } catch (IOException e) {
            throw new UncheckedIOException(e);
        }
    }

    @SuppressWarnings("UnusedReturnValue")
    private static final class ByteBuffer {
        private static final int DEFAULT_BUF_SIZE = 1 << 12;
        private byte[] buf;
        private int ptr = 0;
        private ByteBuffer(@SuppressWarnings("SameParameterValue") int capacity) {
            this.buf = new byte[capacity];
        }
        private ByteBuffer() {
            this(DEFAULT_BUF_SIZE);
        }
        private ByteBuffer append(int b) {
            if (ptr == buf.length) {
                int newLength = buf.length << 1;
                byte[] newBuf = new byte[newLength];
                System.arraycopy(buf, 0, newBuf, 0, buf.length);
                buf = newBuf;
            }
            buf[ptr++] = (byte) b;
            return this;
        }
        private char[] toCharArray() {
            char[] chs = new char[ptr];
            for (int i = 0; i < ptr; i++) {
                chs[i] = (char) buf[i];
            }
            return chs;
        }
        private byte[] getRawBuf() {
            return buf;
        }
        private int size() {
            return ptr;
        }
        private void clear() {
            ptr = 0;
        }
    }
}

/**
 * @author https://atcoder.jp/users/suisen
 */
abstract class ModArithmetic {
    public abstract long getMod();
    public abstract long mod(long a);
    public abstract long add(long a, long b);
    public abstract long sub(long a, long b);
    public abstract long mul(long a, long b);
    public final long div(long a, long b) {return mul(a, inv(b));}
    public final long inv(long a) {
        a = mod(a);
        long b = getMod();
        long u = 1, v = 0;
        while (b >= 1) {
            long t = a / b;
            a -= t * b;
            long tmp1 = a; a = b; b = tmp1;
            u -= t * v;
            long tmp2 = u; u = v; v = tmp2;
        }
        if (a != 1) throw new ArithmeticException("divide by zero");
        return mod(u);
    }
    public final long fma(long a, long b, long c) {return add(mul(a, b), c);}
    public final long pow(long a, long b) {
        long pow = 1;
        for (a = mod(a); b > 0; b >>= 1, a = mul(a, a)) {
            if ((b & 1) == 1) pow = mul(pow, a);
        }
        return pow;
    }

    public final long add(long a, long b, long c) {return mod(a + b + c);}
    public final long add(long a, long b, long c, long d) {return mod(a + b + c + d);}
    public final long add(long a, long b, long c, long d, long e) {return mod(a + b + c + d + e);}
    public final long add(long a, long b, long c, long d, long e, long f) {return mod(a + b + c + d + e + f);}
    public final long add(long a, long b, long c, long d, long e, long f, long g) {return mod(a + b + c + d + e + f + g);}
    public final long add(long a, long b, long c, long d, long e, long f, long g, long h) {return mod(a + b + c + d + e + f + g + h);}
    public final long add(long... xs) {long s = 0; for (long x : xs) s += x; return mod(s);}
    public final long mul(long a, long b, long c) {return mul(a, mul(b, c));}
    public final long mul(long a, long b, long c, long d) {return mul(a, mul(b, mul(c, d)));}
    public final long mul(long a, long b, long c, long d, long e) {return mul(a, mul(b, mul(c, mul(d, e))));}
    public final long mul(long a, long b, long c, long d, long e, long f) {return mul(a, mul(b, mul(c, mul(d, mul(e, f)))));}
    public final long mul(long a, long b, long c, long d, long e, long f, long g) {return mul(a, mul(b, mul(c, mul(d, mul(e, mul(f, g))))));}
    public final long mul(long a, long b, long c, long d, long e, long f, long g, long h) {return mul(a, mul(b, mul(c, mul(d, mul(e, mul(f, mul(g, h)))))));}
    public final long mul(long... xs) {long s = 1; for (long x : xs) s = mul(s, x); return s;}
    /**
     * @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
     */
    public final long[] gcdInv(long a) {
        final long m = getMod();
        a = mod(a);
        if (a == 0) return new long[]{m, 0};
        long s = m, t = a;
        long m0 = 0, m1 = 1;
        while (t > 0) {
            long u = s / t;
            s -= t * u;
            m0 -= m1 * u;
            long tmp;
            tmp = s; s = t; t = tmp;
            tmp = m0; m0 = m1; m1 = tmp;
        }
        if (m0 < 0) m0 += m / s;
        return new long[]{s, m0};
    }
    public final OptionalLong sqrt(long a) {
        a = mod(a);
        if (a == 0) return OptionalLong.of(0);
        if (a == 1) return OptionalLong.of(1);
        long p = getMod();
        if (pow(a, (p - 1) >> 1) != 1) {
            return OptionalLong.empty();
        }
        if ((p & 3) == 3) {
            return OptionalLong.of(pow(a, (p + 1) >> 2));
        }
        if ((p & 7) == 5) {
            if (pow(a, (p - 1) >> 2) == 1) {
                return OptionalLong.of(pow(a, (p + 3) >> 3));
            } else {
                return OptionalLong.of(mul(pow(2, (p - 1) >> 2), pow(a, (p + 3) >> 3)));
            }
        }
        long S = 0, Q = p - 1;
        while ((Q & 1) == 0) {
            ++S;
            Q >>= 1;
        }
        long z = 1;
        while (pow(z, (p - 1) >> 1) != p - 1) ++z;
        long c = pow(z, Q), R = pow(a, (Q + 1) / 2), t = pow(a, Q), M = S;
        while (t != 1) {
            long cur = t;
            int i;
            for (i = 1; i < M; i++) {
                cur = mul(cur, cur);
                if (cur == 1) break;
            }
            long b = pow(c, 1L << (M - i - 1));
            c = mul(b, b); R = mul(R, b); t = mul(t, b, b); M = i;
        }
        return OptionalLong.of(R);
    }

    public final int primitiveRoot() {
        final int m = Math.toIntExact(getMod());
        if (m == 2) return 1;
        if (m == 167772161) return 3;
        if (m == 469762049) return 3;
        if (m == 754974721) return 11;
        if (m == 998244353) return 3;
        int[] divs = new int[20];
        divs[0] = 2;
        int cnt = 1;
        int x = (m - 1) / 2;
        while (x % 2 == 0) x /= 2;
        for (int i = 3; (long) i * i <= x; i += 2) {
            if (x % i == 0) {
                divs[cnt++] = i;
                while (x % i == 0) x /= i;
            }
        }
        if (x > 1) {
            divs[cnt++] = x;
        }
        for (int g = 2; ; g++) {
            boolean ok = true;
            for (int i = 0; i < cnt; i++) {
                if (pow(g, (m - 1) / divs[i]) == 1) {
                    ok = false;
                    break;
                }
            }
            if (ok) return g;
        }
    }

    /** array operations */

    public final long[] rangeInv(int n) {
        final long MOD = getMod();
        long[] invs = new long[n + 1];
        if (n == 0) return invs;
        invs[1] = 1;
        for (int i = 2; i <= n; i++) {
            invs[i] = mul(MOD - MOD / i, invs[(int) (MOD % i)]);
        }
        return invs;
    }
    public final long[] arrayInv(long[] a) {
        int n = a.length;
        long[] l = new long[n + 1];
        long[] r = new long[n + 1];
        l[0] = r[n] = 1;
        for (int i = 0; i < n; i++) l[i + 1] = mul(l[i], a[i    ]);
        for (int i = n; i > 0; i--) r[i - 1] = mul(r[i], a[i - 1]);
        long invAll = inv(l[n]);
        long[] invs = new long[n];
        for (int i = 0; i < n; i++) {
            invs[i] = mul(l[i], r[i + 1], invAll);
        }
        return invs;
    }
    public final long[] factorial(int n) {
        long[] ret = new long[n + 1];
        ret[0] = 1;
        for (int i = 1; i <= n; i++) ret[i] = mul(ret[i - 1], i);
        return ret;
    }
    public final long[] factorialInv(int n) {
        long facN = 1;
        for (int i = 2; i <= n; i++) facN = mul(facN, i);
        long[] invs = new long[n + 1];
        invs[n] = inv(facN);
        for (int i = n; i > 0; i--) invs[i - 1] = mul(invs[i], i);
        return invs;
    }
    public final long[] rangePower(long a, int n) {
        a = mod(a);
        long[] pows = new long[n + 1];
        pows[0] = 1;
        for (int i = 1; i <= n; i++) pows[i] = mul(pows[i - 1], a);
        return pows;
    }
    public final long[] rangePowerInv(long a, int n) {
        a = mod(a);
        long[] invs = new long[n + 1];
        invs[n] = inv(pow(a, n));
        for (int i = n; i > 0; i--) invs[i - 1] = mul(invs[i], a);
        return invs;
    }

    /** combinatric operations */

    public final long[][] combTable(int n) {
        long[][] comb = new long[n + 1][];
        for (int i = 0; i <= n; i++) {
            comb[i] = new long[i + 1];
            comb[i][0] = comb[i][i] = 1;
            for (int j = 1; j < i; j++) {
                comb[i][j] = add(comb[i - 1][j - 1], comb[i - 1][j]);
            }
        }
        return comb;
    }
    public final long naiveComb(long n, int r) {
        if (r < 0 || r > n) return 0;
        long num = 1, den = 1;
        for (int i = 0; i < r; i++) {
            num = mul(num, mod(n - i));
            den = mul(den, i + 1);
        }
        return div(num, den);
    }
    public final long naivePerm(long n, long r) {
        if (r < 0 || r > n) return 0;
        long res = 1;
        for (long i = 0; i < r; i++) res = mul(res, n - i);
        return res;
    }
    public final long naiveFactorial(int n) {
        return naivePerm(n, n);
    }
}