AT_k4pc_g.42

水镜王国的卡加米兹王有一个独特的爱好：专攻“出头鸟”。每天，他都会把家臣们排成一排，用他强力的高压水泵猛击那些身高突出的家臣。

作为卡加米兹王的心腹，你注意到他选择攻击目标时，并不是单纯地挑选身高最高的家臣。

卡加米兹王的原则是：“不论在何事上，中庸之道最为重要。在队列中，除了队首和队尾以外，每个人的身高必须等于两边相邻人的身高平均值。”

这样，卡加米兹王在完成他的高压水泵“艺术”后，看到整个队列中每个家臣的身高都符合这个平均值规则，就会感到非常高兴。

你目睹这一幕幕，不禁思考，到底有多少种排列方式能让这一规则成立呢？为了更好地估算数量，你决定给每个家臣的身高设定一个上下限值。

在水镜王国，家臣的身高总是整数，也有一些身高可能是零或者负数。

输入一行数据：$N$ $A_1$ … $A_N$ $B_1$ … $B_N$ 。其中，$N$ 是整数，代表家臣的数量。而后为两个长度为 $N$ 的整数序列 $A$ 和 $B$，分别表示每个家臣允许的最小和最大身高。

输出满足条件的身高排列的方案数，并对 $1,000,000,007$ 取模。

给定的两个长度为 $N$ 的整数序列 $A$ 和 $B$，求出满足以下条件的长度为 $N$ 的整数序列 $X$ 的数量。答案需要对 $1,000,000,007$ 取模。

• 对于所有 $i = 1, \ldots, N$，满足 $A_i \le X_i \le B_i$。
• 对于所有 $i = 2, \ldots, N - 1$，满足 $X_i = \frac{X_{i-1} + X_{i+1}}{2}$。

输入数据保证：

• $3 \le N \le 10^5$。
• $-10^9 \le A_i \le B_i \le 10^9$。

在部分数据中（2分），满足额外条件：

• $N \le 100$。
• $-100 \le A_i \le B_i \le 100$。

示例解释

例如，在以下示例中，满足条件的5种排列为：

• $X_1 = 0, X_2 = 0, X_3 = 0$
• $X_1 = 0, X_2 = 1, X_3 = 2$
• $X_1 = 1, X_2 = 1, X_3 = 1$
• $X_1 = 2, X_2 = 1, X_3 = 0$
• $X_1 = 2, X_2 = 2, X_3 = 2$

在其他某个示例中，满足条件的排列数多达 $2,000,000,002,000,000,001$ 种。请一定记得在输出结果时取模 $1,000,000,007$。

本翻译由 AI 自动生成