格雷码

题号：NC204351
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

格雷码是指在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，并且首尾两个数也满足这个性质。例如4个数的一种格雷码为 $(00),(01),(11),(10)$ 。小G在学习格雷码的时候萌生了一个想法。如果一个数列满足除了首尾以外最多有一位不同，而首尾必须恰好有一位不同，则小G将其称为格雷序列。小G想知道长度为 $n$ ，每个数范围都在 $0-2^k-1$ 的格雷序列有多少个？同时，他增加了一些限制，因为在格雷序列里他不想让某些 $y$ 出现在 $x$ 后面（注意第一个数被认为是出现在第 $n$ 个数后面）。

输入描述:

第一行三个数 $n,k,m(1 \leq n \leq 10^9,1 \leq k \leq 6,m \geq 0)$ ，表示格雷序列的长度，每个数的范围，小G增加的限制个数。

接下来 $m$ 行，每行两个数 $x,y$ 表示 $y$ 不能出现在 $x$ 后面。

输出描述:

一个数，表示满足条件的格雷序列数量，对取模。

示例1

输入

复制

2 2 2
0 1
3 2

输出

复制

说明

样例中满足条件的格雷序列有，二进制表示为。