P8322 "JROI-4" Girl's Necro-Fantasy

[Original background of this problem](https://www.luogu.com.cn/paste/imhwx32x) ["Girl's Necro-Fantasy"](https://thwiki.cc/%E5%B0%91%E5%A5%B3%E5%B9%BB%E8%91%AC_%EF%BD%9E_Necro-Fantasy) is the theme song of Yakumo Ran. It is also the battle music for the boss of the extra stage in *Touhou Youyoumu*. It is one of the most classic pieces among the music using the "ZUN trumpet" (ZUN 号). The piano seems to depict a powerful and beautiful beast, and the bright ZUN trumpet, together with Ran's gorgeous bullet patterns, brings the theme of death to its peak.

Given a sequence $a$ of length $n$, and the value range $[l_i,r_i]$ for the $i$-th number $a_i$. Now Ran wants to know how many sequences $a$ satisfy, for a given constant $k$, that: - The greatest common divisor of any two adjacent numbers is not $k$. - The greatest common divisor of any three adjacent numbers is exactly $k$. Since the answer may be very large, output its value $\bmod \space998244353$.

The first line contains two integers $n,k$. In the next $n$ lines, each line contains two integers, representing $l_i,r_i$.

One line: the answer modulo $998244353$.

[Sample Explanation] For sample $1$, the valid sequences are: $[2,6,3],[3,6,4],[4,6,3]$. [Constraints and Conventions] - Subtask 1 (7 pts): $3 \leq n \leq 5$, $1 \leq m \leq 10$. - Subtask 2 (23 pts): $3 \leq n \leq 100$, $1 \leq m \leq 100$. - Subtask 3 (25 pts): $3 \leq n \leq 1000$, $1 \leq m \leq 1000$. - Subtask 4 (45 pts): no special restrictions. For $100\%$ of the data, $3 \leq n \leq 2000$, $1 \leq l_i \leq r_i \leq 5000$, $1 \leq k \leq 5000$. Here, $m=\max_{i=1}^{n}r_i$. Translated by ChatGPT 5