Background

Original background of this problem

"Girl's 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.

Problem Description

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$.

Input Format

The first line contains two integers $n,k$.

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

Output Format

One line: the answer modulo $998244353$.

3 1
1 6
2 6
3 6

3

4 1
11 45
19 81
31 53
7 28

6295

Hint

[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