import sys
MOD = 998244353

def main():
    N, K = map(int, sys.stdin.readline().split())
    M = int(sys.stdin.readline())
    intervals = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
    
    intervals.sort()
    
    from itertools import combinations
    total = 0
    for m in range(1, M+1):
        for S in combinations(intervals, m):
            current = []
            for L, R in S:
                if not current:
                    current.append([L, R])
                else:
                    if L > current[-1][1]:
                        current.append([L, R])
                    else:
                        merged_L = current[-1][0]
                        merged_R = max(current[-1][1], R)
                        current[-1] = [merged_L, merged_R]
            total_union = 0
            for L, R in current:
                total_union += R - L + 1
            X = K - total_union
            term = pow(X, N, MOD)
            if m % 2 == 1:
                total = (total + term) % MOD
            else:
                total = (total - term) % MOD
    ans = (pow(K, N, MOD) - total) % MOD
    print(ans if ans >= 0 else ans + MOD)

if __name__ == "__main__":
    main()