THE SOLUTION MUST BE IN C++

DO NOT COPY ANSWERS FROM CHEGG OR OTHER WEBSITES BECAUSE ARE WRONG!

THANKS!

Reinhold is a geneticist who examines how molecules combine to form DNA, which contains all of life's information. He understands that DNA must include at least N molecules in order to create a specific creature. Despite the fact that natural DNA is made up of just four molecules, he discovered that in his laboratory, he can combine M molecules to make artificial DNA.

However, there are significant limitations, such as the inability to connect certain molecules one after the other. For example, the restriction (A, D), can not combine molecules a and d to form AD, but it can combine them and form DA or ATD. A valid DNA is any combination of M molecules of length N that satisfies all K constraints.

Reinhold needs to figure out how many different molecule combinations of length N can make up a valid DNA strand. Because this is such a huge number, he will expect as a result the rest of the division of this number (modulo) by 666013.

Data format:

Input:

The input file is called dna.in.

The first line contains 3 numbers: N, M and K.

Then the on the next K lines: on each line there are 2 numbers, i and j, that signify the existence of the constraint (Ai, Aj).

Output:

The output file is called dna.out.

Only one number will be written in the output file, that represents the number of valid combinations of length N modulo 666013.

The operation A modulo B represents the rest of the division of A to B.

The operation has the following properties:

(A + B) % C = ((A % C) + (B % C)) % C

(A * B) % C = ((A % C) * (B % C)) % C

Data limits:

1

1

1

For all restrictions (Ai, Aj), we have 1

Time limits on vmchecker: C++ (0.5 s)

When submitting the solution, please name the source file: dna.cpp

Example 1: dna.in dna.out 221 3 12 Explanation Example 1: If molecule 1 is A and molecule 2 is D then there are 3 valid DNA strands with the length 2 that can be formed with 2 molecules: AA, DA, DD. And 3 modulo 666013 equals 3. Example 2: dna.in dna.out 332 15 12 3 32 Explanation - Example 2: The following 15 combinations of molecules can be formed: 111, 113, 131, 133, 211, 213, 221, 222, 223, 231, 233, 311, 313, 331, 33 3. And 15 modulo 666013 equals 15