oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

magnets Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

magnets.html

Problem Description

Jie Feng the Physics Whiz has just invented some new magnets. These magnets are cubic in shape come in C different colours, numbered from 1 to C.

Two magnets can either attract or repel each other when they are placed next to each other. Jie Feng knows that there are R distinct ordered pairs of colours of magnets (Ai, Bi) that will repel each other. The two magnets will only repel each other when the magnet of colour Bi is placed after the magnet of colour Ai.

Jie Feng wants to construct a bar magnet of N of the new magnets. He can use any number of any type of magnets. However, he must ensure that no two adjacent magnets in the bar magnet repel each other.

Jie Feng wants you to help him calculate how many distinct bar magnets he can make. Help him calculate this number, modulo 109 + 7.

Input

The first line of input will contain three integers, N, C and R.

The next R lines of input will contain two integers each, Ai and Bi.

Output

Output a single integer, the number of distinct bar magnets, modulo 109 + 7.

Limits

For all subtasks, 1 ≤ Ai, Bi ≤ C. 0 ≤ R ≤ C2

Subtask 1 (23%): 1 ≤ N ≤ 1015. 1 ≤ C ≤ 52. R = 0.

Subtask 2 (19%): 1 ≤ N ≤ 8. 1 ≤ C ≤ 9.

Subtask 3 (25%): 1 ≤ N ≤ 15. 1 ≤ C ≤ 15.

Subtask 4 (33%): 1 ≤ N ≤ 1015. 1 ≤ C ≤ 52.

Subtask 5 (0%): Sample Testcases

Sample Testcase 1

Input

3 3 2
1 2
2 1

Output

17

Tags

Math

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
123201s64MBMinimum
219301s64MBMinimum
325301s64MBMinimum
433301s64MBMinimum
5011s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o magnets -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.