#include <cstdio>
#include <cstdint>
#include <cassert>
#include <utility>

static const uint64_t MODULUS = 1000 * 1000 * 1000 + 7;
static uint8_t numbers[2 * 1000 * 1000 + 1];
static uint32_t factorials[4 * 1000 * 1000 + 1];
static uint32_t inverse_factorials[4 * 1000 * 1000 + 1];
static uint32_t inverses[4 * 1000 * 1000 + 1];
static uint32_t pows_of_two[4 * 1000 * 1000 + 1];
static uint32_t inverse_pows_of_two[4 * 1000 * 1000 + 1];

constexpr static uint32_t add_wrapping(uint32_t a, uint32_t b) {
    return (uint64_t(a) + uint64_t(b)) % MODULUS;
}

// constexpr static uint32_t neg_wrapping(uint32_t a) {
//     return (MODULUS - uint64_t(a)) % MODULUS;
// }

constexpr static uint32_t mul_wrapping(uint32_t a, uint32_t b) {
    return (uint64_t(a) * uint64_t(b)) % MODULUS;
}

constexpr static std::pair<int32_t, int32_t> extended_euclid(int32_t a, int32_t b) {
    if (b == 0) {
        return {1, 0};
    } else {
        const auto [x, y] = extended_euclid(b, a - (a / b) * b);
        return {y, x - (a / b) * y};
    }
}

constexpr static uint32_t inverse_wrapping(uint32_t a) {
    auto [x, y] = extended_euclid(MODULUS, a);
    if (y < 0) {
        y += MODULUS;
    }
    return y;
}

uint32_t solve() {
    int n;
    scanf("%d", &n);

    int seen = 0;
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        assert(x >= 0 && x <= 2);
        assert(y >= 0 && y <= 2);
        seen |= 1 << x;
        seen |= 1 << y;
        numbers[2*i+0] = x;
        numbers[2*i+1] = y;
    }

    if ((seen & (1 << 0)) && (seen & (1 << 2))) {
        // No valid solution if both 0 and 2 appears in the input
        return 0;
    }

    if (seen & (1 << 2)) {
        int prev = numbers[2*n-1];
        for (int i = 0; i <= n; i++) {
            int curr = numbers[i];
            numbers[i] = 2 - prev;
            prev = curr;
        }
        if (seen & (1 << 2)) {
            seen -= (1 << 2);
            seen += (1 << 0);
        }
    }
    // Now, all values are either 0 or 1

    // Precompute stuff
    // TODO: Only calculate what's needed, reuse results from the previous test case
    factorials[0] = 1;
    inverses[0] = 0;
    inverse_factorials[0] = 1;
    pows_of_two[0] = 1;
    inverse_pows_of_two[0] = 1;
    const uint32_t inverse_2 = inverse_wrapping(2);
    for (int i = 1; i <= 4*n; i++) {
        factorials[i] = mul_wrapping(i, factorials[i-1]);
        inverses[i] = inverse_wrapping(i);
        inverse_factorials[i] = mul_wrapping(inverses[i], inverse_factorials[i-1]);
        pows_of_two[i] = mul_wrapping(pows_of_two[i-1], 2);
        inverse_pows_of_two[i] = mul_wrapping(inverse_pows_of_two[i-1], inverse_2);

        // fprintf(stderr,
        //         "[%d] factorials: %d, inverses: %d, inverse_factorials: %d, pows_of_two: %d, inverse_pows_of_two: %d\n",
        //         i, factorials[i], inverses[i], inverse_factorials[i], pows_of_two[i], inverse_pows_of_two[i]);
    }

    if (seen == (1 << 0)) {
        // Special case: all zeros
        // We need to count all possible card configurations where the team A
        // has two best cards.

        // For the best two cards, select two unique players (n * (n - 1))
        const uint32_t best_two_different_player_choices = mul_wrapping(n, n - 1);
        // Choose the configuration for remaining cards
        const uint32_t remaining_choices_for_two_different_players = (n > 1)
                ? mul_wrapping(factorials[4*n-2], inverse_pows_of_two[2*n-2])
                : 0;

        // Alternatively, select one player and give them two cards
        const uint32_t best_one_same_player_choices = n;
        // Choose the configuration for remaining cards
        const uint32_t remaining_choices_for_one_same_player = mul_wrapping(factorials[4*n-2], inverse_pows_of_two[2*n-1]);

        // fprintf(stderr, "best two different player choices: %d\n", best_two_different_player_choices);
        // fprintf(stderr, "remaining choices for two different players: %d\n", remaining_choices_for_two_different_players);
        // fprintf(stderr, "best one same player choices: %d\n", best_one_same_player_choices);
        // fprintf(stderr, "remaining choices for one same player: %d\n", remaining_choices_for_one_same_player);

        return add_wrapping(
            mul_wrapping(best_two_different_player_choices, remaining_choices_for_two_different_players),
            mul_wrapping(best_one_same_player_choices, remaining_choices_for_one_same_player)
        );
    } else if (seen == (1 << 1)) {
        // Special case: all ones

        // Two variants: either A has the best card and B has two following cards,
        // or vice versa. The cases are completely symmetric so we'll just multiply
        // by two.
        const uint32_t second_best_two_player_choices = mul_wrapping(n, n - 1);
        const uint32_t second_best_one_player_choices = n;

        // fprintf(stderr, "second best two player choices: %d\n", second_best_two_player_choices);
        // fprintf(stderr, "second best one player choices: %d\n", second_best_one_player_choices);

        const uint32_t configs_without_best = add_wrapping(
            (n > 1) ? mul_wrapping(second_best_two_player_choices, mul_wrapping(factorials[4*n-3], inverse_pows_of_two[2*n-3])) : 0,
            mul_wrapping(second_best_one_player_choices, mul_wrapping(factorials[4*n-3], inverse_pows_of_two[2*n-2]))
        );

        // fprintf(stderr, "configs without best: %d\n", configs_without_best);

        // Account for the best card here
        return mul_wrapping(2 * n, configs_without_best);
    } else {
        // General case

        // Count the groups of ones, also do verification
        int num_groups = 0;
        int canonical_gap_start = 0;
        for (int i = 0; i < n; i++) {
            const int x = numbers[2*i+0];
            const int y = numbers[2*i+1];
            if (x == 0 && y == 1) {
                // Impossible case
                return 0;
            } else if (x == 1 && y == 1) {
                const int ii = (i + 1) % n;
                if (numbers[2*ii+0] == 0) { // No need to check y == 0, it's implied by x
                    // Improperly terminated group
                    return 0;
                }
            } else if (x == 1 && y == 0) {
                // Group terminator
                num_groups++;
                canonical_gap_start = i+1;
            }
        }

        uint32_t paa_count = 0;

        // Align with a start of a gap, then look at how big the gaps are
        int last_group_start = 0;
        for (int j = 0; j < n; j++) {
            const int i = (canonical_gap_start + j) % n;
            const int x = numbers[2*i+0];
            if (x == 0) { // No need to check y == 0, it's implied by x
                if (j > last_group_start) {
                    // Choose one P, choose two A
                    paa_count = add_wrapping(paa_count, mul_wrapping(j - last_group_start, mul_wrapping(j - last_group_start, j - last_group_start)));
                }
                last_group_start = j + 1;
            }
        }

        // fprintf(stderr, "Groups: %d\n", num_groups);
        // fprintf(stderr, "PAA count: %u\n", paa_count);

        uint32_t result = 0;

        // Variant 1: normal stairs, 2P just below
        // Choose the highest 2 P players, then choose the rest arbitrarily
        uint32_t choices_of_2p = 0;
        if (num_groups <= n - 2) {
            choices_of_2p = add_wrapping(choices_of_2p, mul_wrapping(
                // Choose two of not chosen for any group
                mul_wrapping(n - num_groups, n - num_groups),
                mul_wrapping(
                    factorials[4*n - 2 * num_groups - 2],
                    inverse_pows_of_two[2*n - 2 * num_groups - 2]
                )
            ));
            // fprintf(stderr, "Choices of 2P after including out-group units: %u\n", choices_of_2p);
        }
        if (num_groups <= n - 1) {
            choices_of_2p = add_wrapping(choices_of_2p, mul_wrapping(
                // Choose one from the groups and the other from others
                mul_wrapping(num_groups, n - num_groups),
                mul_wrapping(
                    factorials[4*n - 2 * num_groups - 1],
                    inverse_pows_of_two[2*n - 2 * num_groups - 1]
                )
            ));
            // fprintf(stderr, "Choices of 2P after including out-and-not-out-group units: %u\n", choices_of_2p);
        }
        choices_of_2p = add_wrapping(choices_of_2p, mul_wrapping(
            // Choose both from the groups
            mul_wrapping(num_groups, num_groups),
            mul_wrapping(
                factorials[4*n - 2 * num_groups],
                inverse_pows_of_two[2*n - 2 * num_groups]
            )
        ));
        // fprintf(stderr, "Choices of 2P after including ingroup units: %u\n", choices_of_2p);

        result = add_wrapping(result, mul_wrapping(num_groups, choices_of_2p));
        // fprintf(stderr, "Result now is: %u\n", result);

        // Variant 2: one stair is substituted by this horrible PAA thing
        // Not implemented!
        // fprintf(stderr, "Result now is: %u\n", result);

        return result;
    }

    return 0;
}

int main() {
    int t;
    scanf("%d", &t);

    while (t --> 0) {
        printf("%llu\n", (unsigned long long int)solve());
    }

    return 0;
}