#P18177. Penguins in Refrigerator

Penguins in Refrigerator

Penguins in Refrigerator

有 nn 只企鹅,编号为 1,2,…,n1,2,\ldots,n。编号为 ii 的企鹅宽度为 wiw_i。它们按照排列 pp 依次进入冰箱:第 ii 个进入的是编号 pip_i 的企鹅。

冰箱宽度为 WW,深度视为无限。所有企鹅进入后,如果相邻两只企鹅的宽度之和不超过 WW,它们就可以交换位置。可以进行任意多次这样的交换,同一只企鹅也可以参与多次交换。

冰箱只有一扇门,采用后进先出的方式:如果不进行交换,企鹅的出门顺序为 pn,pn−1,…,p1p_n,p_{n-1},\ldots,p_1。

请计算所有可能的不同出门顺序的数量,并求出其中字典序最小的顺序。每只企鹅按编号区分,宽度相同的企鹅仍是不同的企鹅;同一个最终顺序只计一次,不按交换操作序列计数。

两个排列的字典序按从左往右第一个不同位置的企鹅编号比较,编号较小的排列字典序较小。

输入格式

第一行两个整数 n,Wn,W,满足 1≤n≤1061\le n\le10^6、1≤W≤1091\le W\le10^9。

第二行 nn 个整数 p1,p2,…,pnp_1,p_2,\ldots,p_n,表示进入冰箱的顺序。保证它们是 1,2,…,n1,2,\ldots,n 的一个排列。

第三行 nn 个整数 w1,w2,…,wnw_1,w_2,\ldots,w_n,满足 1≤wi≤W1\le w_i\le W。注意宽度按企鹅编号给出。

输出格式

第一行输出不同出门顺序的数量,对 109+710^9+7 取模。

第二行输出 nn 个整数,表示字典序最小的出门顺序。

样例 1

输入:

5 10
1 2 3 4 5
6 5 3 9 2

输出:

3
5 4 2 1 3

样例 2

输入:

5 10
1 2 3 4 5
2 4 3 3 8

输出:

30
1 5 2 3 4