Counting Distinct Interval Minimum Sequences

Problem Statement

You are given a positive integer sequence a of length n, where each element satisfies 1 ≤ a_i ≤ c. In addition, you are provided with m intervals [l_i, r_i] (1-indexed). For each interval, define b_i = \(\min_{j=l_i}^{r_i}a_j\). The sequence b has length m. Your task is to count, over all possible sequences a (with each element in the range [1, c]), how many distinct sequences b can be produced. Since the answer can be large, output it modulo \(998244353\).

Note:

All formulas are given in LaTeX format. For example, the modulo is given by \(998244353\) and the minimum over the interval is defined as \(b_i = \min_{j=l_i}^{r_i}a_j\).

inputFormat

Input Format

The first line contains three integers: n, m, and c.
Each of the next m lines contains two integers l and r representing an interval \([l, r]\) (1-indexed).

Constraints are such that it is feasible to enumerate over all sequences a when solving the problem using brute force techniques.

outputFormat

Output Format

Output a single integer, the number of distinct sequences b that can be obtained from all possible sequences a, taken modulo \(998244353\).

sample

3 2 3
1 2
2 3

9