import java.math.BigInteger;
import java.util.Scanner;

public class Solution2 {

    private static final int MAX_K = 1002;
    public static final int INT_MODULO = 1000000009;
    private static BigInteger[][] memo = new BigInteger[MAX_K][MAX_K];
    private static MegaRatio[] bernoulli = new MegaRatio[MAX_K];
    private static int maxComputedBernoulli = 0;

    private static int highwayConstruction(long n, int k) {
        if (Math.pow(k, 2) > n) {
            BigInteger result = BigInteger.ZERO;
            for (long i = 2; i < n; i++) {
                result = result.add(BigInteger.valueOf((long) Math.pow(i, k)));
            }
            return result.mod(BigInteger.valueOf(INT_MODULO)).intValue();
        }
        MegaRatio result = MegaRatio.ZERO;
        if (k > maxComputedBernoulli) {
            computeBernoulli(k + 1);
            maxComputedBernoulli = k + 1;
        }
        for (int i = 1, j = k + 1; i <= k + 1; i++, j--) {
            if (i - 1 > 2 && i - 1 % 2 == 1)
                continue;
            MegaRatio coef = calcCoef(i, k, bernoulli);
            if (!result.denom.equals(coef.denom)) {
                result.num = result.num.add(coef.denom.multiply(
                        coef.num.multiply(BigInteger.valueOf((long) Math.pow(n - 1, j)))));
                result.denom = result.denom.multiply(coef.denom);
            } else {
                result.num = result.num.add(
                        coef.num.multiply(BigInteger.valueOf((long) Math.pow(n - 1, j))));
            }
        }
        return result.decimalValue()
                .subtract(BigInteger.ONE)
                .mod(BigInteger.valueOf(INT_MODULO))
                .intValue();
    }

    private static MegaRatio calcCoef(int i, int k, MegaRatio[] bernoulli) {
        MegaRatio ber_nbre = bernoulli[i - 1];
        return new MegaRatio(combination(k + 1, i - 1).multiply(BigInteger.valueOf((long) Math.pow(-1, i - 1)))
                .multiply(ber_nbre.num), ber_nbre.denom.multiply(BigInteger.valueOf(k + 1)));
    }

    private static BigInteger combination(int n, int k) {
        return comb(BigInteger.valueOf(n), BigInteger.valueOf(k));
    }


    private static BigInteger comb(BigInteger n, BigInteger k) {
        if (n.intValue() == 0 && k.intValue() > 0) {
            return BigInteger.ZERO;
        } else if (k.intValue() == 0 && n.intValue() >= 0) {
            return BigInteger.ONE;
        } else if (memo[n.intValue()][k.intValue()] != null) {
            return memo[n.intValue()][k.intValue()];
        } else {
            memo[n.intValue()][k.intValue()] =
                    comb(n.subtract(BigInteger.ONE), k.subtract(BigInteger.ONE))
                            .add(comb(n.subtract(BigInteger.ONE), k));
        }
        return memo[n.intValue()][k.intValue()];

    }

    private static void computeBernoulli(int m) {
        long[][] binomial = new long[m + 1][m + 1];
        for (int n = 1; n <= m; n++) binomial[0][n] = 0;
        for (int n = 0; n <= m; n++) binomial[n][0] = 1;

        for (int n = 1; n <= m; n++)
            for (int k = 1; k <= m; k++)
                binomial[n][k] = binomial[n - 1][k - 1] + binomial[n - 1][k];

        if (maxComputedBernoulli == 0) {
            bernoulli[0] = new MegaRatio(BigInteger.valueOf(1), BigInteger.valueOf(1));
            bernoulli[1] = new MegaRatio(BigInteger.valueOf(-1), BigInteger.valueOf(2));
            for (int k = 2; k < m; k++) {
                bernoulli[k] = MegaRatio.ZERO;
                calcKthBernoulli(binomial, k);
            }
        } else {
            for (int k = maxComputedBernoulli + 1; k < m; k++) {
                bernoulli[k] = MegaRatio.ZERO;
                calcKthBernoulli(binomial, k);
            }
        }

    }

    private static void calcKthBernoulli(long[][] binomial, int k) {
        if (k % 2 == 0) {
            bernoulli[k] = MegaRatio.ZERO;
            for (int i = 0; i < k; i++) {
                MegaRatio coef = new MegaRatio(BigInteger.valueOf(binomial[k + 1][k + 1 - i]), BigInteger.valueOf(1));
                bernoulli[k] = bernoulli[k].subtract(coef.times(bernoulli[i]));
            }
            bernoulli[k] = bernoulli[k].divide(new MegaRatio(BigInteger.valueOf(k + 1), BigInteger.valueOf(1)));
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        for (int a0 = 0; a0 < q; a0++) {
            long n = in.nextLong();
            int k = in.nextInt();
            int result = highwayConstruction(n, k);
            System.out.println(result);
        }
        in.close();
    }
}

class MegaRatio {
    final static MegaRatio ZERO = new MegaRatio(BigInteger.ZERO, BigInteger.ONE);
    BigInteger num, denom;

    MegaRatio(BigInteger num, BigInteger denom) {
        this.num = num;
        this.denom = denom;
    }

    private static MegaRatio canonical(BigInteger num, BigInteger denom, boolean checkGcd) {
        if (denom.signum() == 0) {
            throw new IllegalArgumentException("");
        }
        if (num.signum() == 0) {
            return ZERO;
        }
        if (denom.signum() < 0) {
            num = num.negate();
            denom = denom.negate();
        }
        if (checkGcd) {
            BigInteger gcd = num.gcd(denom);
            if (!gcd.equals(BigInteger.ONE)) {
                num = num.divide(gcd);
                denom = denom.divide(gcd);
            }
        }
        return new MegaRatio(num, denom);
    }

    public MegaRatio add(MegaRatio o) {
        if (o.num.signum() == 0) {
            return this;
        } else if (num.signum() == 0) {
            return o;
        } else if (denom.equals(o.denom)) {
            return new MegaRatio(num.add(o.num), denom);
        } else {
            return canonical(num.multiply(o.denom).add(o.num.multiply(denom)), denom.multiply(o.denom), true);
        }
    }

    public MegaRatio multiply(MegaRatio o) {
        if (num.signum() == 0 || o.num.signum() == 0) {
            return ZERO;
        } else if (num.equals(o.denom)) {
            return canonical(o.num, denom, true);
        } else if (o.num.equals(denom)) {
            return canonical(num, o.denom, true);
        } else if (num.negate().equals(o.denom)) {
            return canonical(o.num.negate(), denom, true);
        } else if (o.num.negate().equals(denom)) {
            return canonical(num.negate(), o.denom, true);
        } else {
            return canonical(num.multiply(o.num), denom.multiply(o.denom), true);
        }
    }

    public boolean isInteger() {
        return num.signum() == 0 || denom.equals(BigInteger.ONE);
    }

    public BigInteger decimalValue() {
        return num.divide(denom);
    }

    public MegaRatio negate() {
        return new MegaRatio(num.negate(), denom);
    }

    public MegaRatio subtract(MegaRatio o) {
        return add(o.negate());
    }

    public MegaRatio invert() {
        return canonical(denom, num, false);
    }

    public MegaRatio times(MegaRatio b) {
        MegaRatio a = this;

        MegaRatio c = new MegaRatio(a.num, b.denom);
        MegaRatio d = new MegaRatio(b.num, a.denom);
        return new MegaRatio(c.num.multiply(d.num), c.denom.multiply(d.denom));
    }

    public MegaRatio divide(MegaRatio o) {
        return multiply(o.invert());
    }
}