题目描述

在遥远的 S 市共有 $n$ 所中学，现在 S 市各中学邀请神犇去进行交（tan）流（xiao）活（feng）动（sheng），神犇决定去每所中学的礼堂开一次讲座，但每所中学的礼堂容量有限，第 $i$ 所中学的礼堂能容纳 $x_i$ 名学生。学生只能在自己的学校听讲。神犇知道每所中学的学生总数，第 $i$ 所中学有 $c_i$ 名学生。现在神犇想知道共有多少种听讲的方案。每个礼堂都不能有空位剩余。两个方案不同当且仅当存在一名学生在一种方案中参加了活动而另一种方案中没有参加。由于答案很大，神犇只需要你告诉他答案模 $p$ 的值（$p$ 不一定是质数）。

输入格式

第一行两个整数 $n$、$p$，表示学校数量和模数。
第二行 $n$ 个整数 $x_1, x_2 \ldots x_n$，表示每所学校礼堂的容量。
第三行 $n$ 个整数 $c_1, c_2 \ldots c_n$，表示每所学校学生总数。

输出格式

输出共一行一个整数，表示总方案数模 $p$ 的值。

样例

input

2 10000000
1 2
100 2000

output

9900000

数据范围与提示

UPD：2018.2.2 新加数据 3 组，已重测。