Counting Special Sequences

You are given a sequence a of length \(n\). For each index \(i\) (1-based), the element \(a_i\) can take any integer value in the range \([l_i, r_i]\). In addition, a constant \(k\) is given. A sequence \(a\) is called special if it satisfies the following two conditions:

• For every two consecutive elements, the greatest common divisor (GCD) is not equal to \(k\); that is, \(\gcd(a_i, a_{i+1}) \neq k\) for all \(1 \le i < n\).
• For every three consecutive elements, the GCD is exactly \(k\); that is, \(\gcd(a_i, a_{i+1}, a_{i+2}) = k\) for all \(1 \le i < n-1\).

Notice that in order for \(\gcd(a_i,a_{i+1},a_{i+2})\) to equal \(k\), it is necessary that every \(a_i\) is a multiple of \(k\). Hence, one may write \(a_i = k \cdot b_i\), and after a simple transformation the conditions become:

• For every two consecutive \(b\) values, \(\gcd(b_i, b_{i+1}) \neq 1\).
• For every three consecutive \(b\) values, \(\gcd(b_i, b_{i+1}, b_{i+2}) = 1\).

The allowed range for \(b_i\) becomes \([\lceil l_i/k \rceil, \lfloor r_i/k \rfloor]\). Compute the number of special sequences \(a\) modulo \(998244353\).

inputFormat

The first line contains two integers \(n\) and \(k\). The following \(n\) lines each contain two integers \(l_i\) and \(r_i\), representing the allowed range for \(a_i\).

Note: It is guaranteed that each \(a_i\) which appears in a special sequence must be a multiple of \(k\).

outputFormat

Output a single integer, which is the number of special sequences modulo \(998244353\).

sample

3 2
2 4
2 4
2 4

0