#P15834. 多项式因式分解
多项式因式分解
题目描述
给定一个多项式 ,以如下形式给出 的若干项系数:
其中 两两不同,没有给出的位置系数均为 。
请计数将 分解成如下形式的方案数:
其中:
答案对 取模。
两种方案不同,当且仅当序列 至少存在一个位置不同。
题目保证至少存在一种合法分解方案。
输入格式
第一行一个正整数 。
接下来 行,每行两个整数 ,表示:
输出格式
输出一行一个整数,表示分解方案数对 取模后的结果。
样例输入
5
-2 1
-1 2
0 2
1 2
2 1
样例输出
2
样例解释
给出的多项式为:
它有如下两种分解方式:
以及:
因此答案为 。
数据范围与子任务
对于所有数据,保证:
子任务如下:
| 子任务 | 分值 | 特殊限制 |
|---|---|---|
| 1 | ||
| 2 | 20 | $ |
| 3 | 79 | 无特殊限制 |