题目描述

你正在爬一座山，山的高度为 $n+1$ 千米。在海拔为

千米的地方都设有哨站。

哨站分为普通哨站和核心哨站。保证核心哨站的数量最多为 $m$，且海拔为 $0,n,n+1$ 千米的哨站均为普通哨站。

每个哨站都有一个指示变量 $c_i$，初始时所有 $c_i=1$。

用变量 $w$ 表示你的努力值，初始时 $w=0$。

当你位于某个哨站 $i$ 时，按照如下规则行动：

• 如果 $i=n+1$，则登顶成功，过程结束，此时的 $w$ 即为你付出的努力；
• 否则，如果 $i=0$，则直接爬到哨站 $i+1$，并令

• 否则，若 $1\le i\le n$，则先令

然后：

• 如果 $c_i=0$，则从哨站 $i$ 爬到哨站 $i+b_i$，并令 $c_i=1$。其中，如果 $i$ 是普通哨站，则 $b_i=1$；否则 $b_i=2$；
• 如果 $c_i=1$，则从哨站 $i$ 掉到哨站 $i-a_i$，并令 $c_i=0$，其中 $1\le a_i\le i$。

请你求出成功登顶所付出的努力值。由于答案可能很大，请输出答案对 $10^9+7$ 取模后的结果。

输入格式

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

第二行包含 $n$ 个整数

第三行包含 $n$ 个整数

输出格式

输出一行一个整数，表示成功登顶所付出的努力值对 $10^9+7$ 取模后的结果。

样例 1

输入

2 0
1 1
1 1

输出

9

样例 2

输入

3 1
1 2 1
2 1 1

输出

11

数据范围与子任务

对于全部数据：

且满足 $b_n=1$。在 $1\sim n-1$ 号哨站中，至多有 $m$ 个位置满足 $b_i=2$。