题目描述

Alice 和 Bob 在玩一个石子游戏。共有 $n$ 堆石子，第 $i$ 堆有 $pile_i$ 个石子，并具有颜色 $color_i$。

两人轮流操作。每次操作可以选择以下两种方式之一：

1. 选择一堆石子，从这一堆中拿走任意正数个石子；
2. 选择一种颜色，从这种颜色的若干堆中一共拿走至少 $1$ 个、至多 $m$ 个石子。石子可以从同色的多堆中分配拿取。

无法操作的人失败。

现在考虑原有 $n$ 堆石子的所有子集。对于每个子集，只保留该子集中的石子堆并由 Alice 先手开始游戏。

请计算有多少个子集使 Alice 必胜，答案对 $998244353$ 取模。

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，每行两个整数 $pile_i,color_i$，表示第 $i$ 堆石子的数量和颜色。

输出格式

输出一个整数，表示 Alice 必胜的子集数量对 $998244353$ 取模后的结果。

数据范围

• $1\le n\le250$；
• $1\le pile_i\le250$；
• $1\le color_i\le250$；
• $1\le m\le250$。

样例 1

2 2
1 1
1 1

3

样例 2

2 2
1 1
1 250

2

样例 3

2 3
2 1
2 1

2