#P18620. Super Meat Bros

Super Meat Bros

Super Meat Bros

《Super Meat Bros》是一部讲述 Meatio 和 Meatigi 两兄弟的漫画,他们都非常喜欢肉。这部漫画的特点是:两兄弟各自拥有独立发展的故事线。

每个兄弟的故事由零个或多个篇章按顺序组成,每个篇章包含 11 到 nn 期漫画。如果一个篇章有 kk 期,漫画家有 aka_k 种不同的方法创作 Meatio 的这个篇章,有 bkb_k 种不同的方法创作 Meatigi 的这个篇章。

漫画家分别创作两条故事线。创作 Meatio 的故事时,他可以重复进行以下操作任意次:选择 1≤k≤n1\le k\le n,从 aka_k 种方案中选择一种,在故事末尾添加一个长为 kk 期的篇章。Meatigi 的故事同理,只是使用 bkb_k 种方案。任一条故事线都允许不包含任何篇章。

两条故事线完成后,漫画家将它们合并为一条故事线。合并必须保留每条原故事线内部各期漫画的先后顺序:如果同一个兄弟的第 xx 期在第 yy 期之前,那么合并后仍必须如此。除此以外,合并顺序可以任意选择。尤其是,同一个篇章的各期在合并后不必连续。

给定 a1,…,ana_1,\ldots,a_n 和 b1,…,bnb_1,\ldots,b_n,求创作一本恰好包含 mm 期漫画的完整单行本的方案数。篇章的划分、各篇章的创作方案以及两条故事线的合并方式均属于方案的组成部分。

输入格式

第一行包含两个整数 n,mn,m,其中 1≤n≤3001\le n\le300,1≤m≤1091\le m\le10^9。

第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n,其中 1≤ai≤1091\le a_i\le10^9。

第三行包含 nn 个整数 b1,…,bnb_1,\ldots,b_n,其中 1≤bi≤1091\le b_i\le10^9。

输入只有一组数据。

输出格式

输出一个整数,表示所求方案数对 109+910^9+9 取模的结果。

样例输入 1

2 3
1 1
1 1

样例输出 1

18

样例输入 2

3 4
1 2 3
1 3 2

样例输出 2

180

样例说明

用小写英文字母表示 Meatio 的漫画期数,用大写英文字母表示 Meatigi 的漫画期数。同一个字母表示属于同一个篇章;各篇章按出现顺序依次使用字母。

第一组样例的 1818 种合并结果为:

abc, abb, aab, ABC, ABB, AAB,
abA, aaA, ABa, AAa, aAB, aAA,
Aab, Aaa, aAb, aAa, AaB, AaA