该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

排球（ball）

【题目描述】

酒狐在一个人打排球。球场可以抽象为一维数轴，有效范围为 $[-m,m]$，球网位于原点 $x=0$。

最开始，球位于 $x=1$。酒狐共有 $n$ 次击球机会，且每一次都必须击球。

第 $i$ 次击球时，她可以选择将球向左击出 $a_i$ 米，或者向右击出 $b_i$ 米。

球每越过一次球网（即从 $x>0$ 变为 $x<0$，或从 $x<0$ 变为 $x>0$），就得到一分。

击球时必须遵守以下规则：

1. 球不能刚好落在球网上，即击球后的坐标不能为 $0$；
2. 球不能飞出球场，即击球后的坐标必须满足 $-m\le x\le m$。

请你求出在不违规的前提下最多能得到多少分，以及在得到最高分的前提下，有多少种不同的击球方法能达到该分数。

输入会给出一个值为 $1$ 或 $2$ 的整数 $op$：

• 当 $op=1$ 时，只需回答最高得分；
• 当 $op=2$ 时，需回答最高得分和获得最高分的方法数，方法数对 $10^9+7$ 取模。

数据保证至少存在一种合法击球方法。

【输入格式】

第一行包含三个整数 $n,m,op$，分别表示击球次数、球场边界和指令类型。

接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i,b_i$，分别表示第 $i$ 次向左和向右击出的距离。

【输出格式】

当 $op=1$ 时，输出一行一个整数，表示最高得分。

当 $op=2$ 时，输出一行两个整数，分别表示最高得分和获得最高分的方法数。

【样例1输入】

3 5 1
4 2
2 3
4 2

【样例1输出】

1

【样例2输入】

3 5 2
4 2
2 3
4 2

【样例2输出】

1 2

【样例解释】

依次选择向左、向右、向左击球，球的位置变化为 $1\to-3\to0\to-4$，但第二次击球后落在球网上，因此这种方法不合法。

得到最高分的两种合法方法是：

• 左、左、右：$1\to-3\to-5\to-3$；
• 右、左、左：$1\to3\to1\to-3$。

两种方法都恰好越过球网一次，所以最高得分为 $1$，共有 $2$ 种最优方法。

【数据范围】

• 对于 $30\%$ 的数据，$n\le20$，$m\le100$，$1\le a_i,b_i\le10$；
• 对于 $100\%$ 的数据，$n\le1000$，$m\le1000$，$1\le a_i,b_i\le100$；
• 测试点中，$op=1$ 与 $op=2$ 的数据各占一半。