I need help with this problem asked in Google Online Challenge.

You are given the following:

- An integer value N

- M pairs of distinct characters (lowercase English alphabets)

A pair of characters in the given pairs holds a relation between them. The relation among the given pairs is also transitive, which means if you consider 2 pairs (u, v) and (v, w) which holds relation, then pair (u, w) also holds the relation. Also, the relation states that those pairs of characters cannot occur together in a formed string.

Determine the total number of strings of length N such that any string does not contain a pair of adjacent characters holding any relation. Since this number can be large output it modulo 10^9+7.

**Constraints**

1 <= T <= 10 (Number of test cases)

1 <= N <= 10^4

0 <= M <= 325 (M is the number of pairs given)

**Example**

Input:

N = 2

M = 3

Pairs = [[a,b], [b,c], [c,d]]

Approach:

- Since [a,b] and [b,c] hold a transitive relation, thus a relation among all pairs in [a, b, c] holds true.

- Since [a, b, c] and [c, d] shares a transitive relation thus a relation among all pairs in [a, b, c, d] holds true.

- So the following pairs cannot occur : [ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc]

- The strings that can be formed of length 2 are : ["aa", "ae", "af", .....]

Output:

664