{"problem":{"name":"G. Flowers and Chocolate","description":{"content":"It's Piegirl's birthday soon, and Pieguy has decided to buy her a bouquet of flowers and a basket of chocolates. The flower shop has _F_ different types of flowers available. The _i_\\-th type of flow","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF866G"},"statements":[{"statement_type":"Markdown","content":"It's Piegirl's birthday soon, and Pieguy has decided to buy her a bouquet of flowers and a basket of chocolates.\n\nThe flower shop has _F_ different types of flowers available. The _i_\\-th type of flower always has exactly _p__i_ petals. Pieguy has decided to buy a bouquet consisting of exactly _N_ flowers. He may buy the same type of flower multiple times. The _N_ flowers are then arranged into a bouquet. The position of the flowers within a bouquet matters. You can think of a bouquet as an ordered list of flower types.\n\nThe chocolate shop sells chocolates in boxes. There are _B_ different types of boxes available. The _i_\\-th type of box contains _c__i_ pieces of chocolate. Pieguy can buy any number of boxes, and can buy the same type of box multiple times. He will then place these boxes into a basket. The position of the boxes within the basket matters. You can think of the basket as an ordered list of box types.\n\nPieguy knows that Piegirl likes to pluck a petal from a flower before eating each piece of chocolate. He would like to ensure that she eats the last piece of chocolate from the last box just after plucking the last petal from the last flower. That is, the total number of petals on all the flowers in the bouquet should equal the total number of pieces of chocolate in all the boxes in the basket.\n\nHow many different bouquet+basket combinations can Pieguy buy? The answer may be very large, so compute it modulo 1000000007 = 109 + 7.\n\n## Input\n\nThe first line of input will contain integers _F_, _B_, and _N_ (1 ≤ _F_ ≤ 10, 1 ≤ _B_ ≤ 100, 1 ≤ _N_ ≤ 1018), the number of types of flowers, the number of types of boxes, and the number of flowers that must go into the bouquet, respectively.\n\nThe second line of input will contain _F_ integers _p_1, _p_2, ..., _p__F_ (1 ≤ _p__i_ ≤ 109), the numbers of petals on each of the flower types.\n\nThe third line of input will contain _B_ integers _c_1, _c_2, ..., _c__B_ (1 ≤ _c__i_ ≤ 250), the number of pieces of chocolate in each of the box types.\n\n## Output\n\nPrint the number of bouquet+basket combinations Pieguy can buy, modulo 1000000007 = 109 + 7.\n\n[samples]\n\n## Note\n\nIn the first example, there is 1 way to make a bouquet with 9 petals (3 + 3 + 3), and 1 way to make a basket with 9 pieces of chocolate (3 + 3 + 3), for 1 possible combination. There are 3 ways to make a bouquet with 13 petals (3 + 5 + 5, 5 + 3 + 5, 5 + 5 + 3), and 5 ways to make a basket with 13 pieces of chocolate (3 + 10, 10 + 3, 3 + 3 + 7, 3 + 7 + 3, 7 + 3 + 3), for 15 more combinations. Finally there is 1 way to make a bouquet with 15 petals (5 + 5 + 5) and 1 way to make a basket with 15 pieces of chocolate (3 + 3 + 3 + 3 + 3), for 1 more combination.\n\nNote that it is possible for multiple types of flowers to have the same number of petals. Such types are still considered different. Similarly different types of boxes may contain the same number of pieces of chocolate, but are still considered different.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Piegirl 的生日快到了，Pieguy 决定为她买一束花和一篮巧克力。\n\n花店有 #cf_span[F] 种不同类型的花。第 #cf_span[i] 种花恰好有 #cf_span[pi] 片花瓣。Pieguy 决定购买恰好 #cf_span[N] 朵花。他可以多次购买同一种花。这 #cf_span[N] 朵花将被排列成一束花。花在花束中的位置很重要。你可以将花束视为一个有序的花类型列表。\n\n巧克力店出售盒装巧克力。共有 #cf_span[B] 种不同类型的盒子。第 #cf_span[i] 种盒子包含 #cf_span[ci] 块巧克力。Pieguy 可以购买任意数量的盒子，也可以多次购买同一种盒子。他将把这些盒子放入一个篮子中。盒子在篮子中的位置很重要。你可以将篮子视为一个有序的盒子类型列表。\n\nPieguy 知道 Piegirl 喜欢在吃每一块巧克力前从一朵花上摘下一片花瓣。他希望确保她在摘下最后一朵花的最后一片花瓣时，正好吃完篮子里最后一个盒子的最后一块巧克力。也就是说，花束中所有花的花瓣总数应等于篮子中所有盒子的巧克力总数。\n\nPieguy 有多少种不同的花束+篮子组合可以购买？答案可能非常大，请对 #cf_span[1000000007 = 109 + 7] 取模。\n\n输入的第一行包含三个整数 #cf_span[F], #cf_span[B], 和 #cf_span[N] #cf_span[(1 ≤ F ≤ 10, 1 ≤ B ≤ 100, 1 ≤ N ≤ 1018)]，分别表示花的种类数、盒子的种类数和花束中必须包含的花朵数量。\n\n第二行包含 #cf_span[F] 个整数 #cf_span[p1, p2, ..., pF] #cf_span[(1 ≤ pi ≤ 109)]，表示每种花的花瓣数量。\n\n第三行包含 #cf_span[B] 个整数 #cf_span[c1, c2, ..., cB] #cf_span[(1 ≤ ci ≤ 250)]，表示每种盒子中的巧克力数量。\n\n请输出 Pieguy 可以购买的花束+篮子组合数，对 #cf_span[1000000007 = 109 + 7] 取模。\n\n在第一个例子中，有 #cf_span[1] 种方式制作出总花瓣数为 #cf_span[9] 的花束 #cf_span[(3 + 3 + 3)]，有 #cf_span[1] 种方式制作出总巧克力数为 #cf_span[9] 的篮子 #cf_span[(3 + 3 + 3)]，共 #cf_span[1] 种组合。有 #cf_span[3] 种方式制作出总花瓣数为 #cf_span[13] 的花束 #cf_span[(3 + 5 + 5, 5 + 3 + 5, 5 + 5 + 3)]，有 #cf_span[5] 种方式制作出总巧克力数为 #cf_span[13] 的篮子 #cf_span[(3 + 10, 10 + 3, 3 + 3 + 7, 3 + 7 + 3, 7 + 3 + 3)]，共 #cf_span[15] 种额外组合。最后，有 #cf_span[1] 种方式制作出总花瓣数为 #cf_span[15] 的花束 #cf_span[(5 + 5 + 5)]，有 #cf_span[1] 种方式制作出总巧克力数为 #cf_span[15] 的篮子 #cf_span[(3 + 3 + 3 + 3 + 3)]，共 #cf_span[1] 种组合。\n\n注意，多种花可能具有相同数量的花瓣，但这些类型仍被视为不同。同样，不同类型的盒子可能包含相同数量的巧克力，但它们仍被视为不同。\n\n## Input\n\n输入的第一行包含三个整数 #cf_span[F], #cf_span[B], 和 #cf_span[N] #cf_span[(1 ≤ F ≤ 10, 1 ≤ B ≤ 100, 1 ≤ N ≤ 1018)]，分别表示花的种类数、盒子的种类数和花束中必须包含的花朵数量。第二行包含 #cf_span[F] 个整数 #cf_span[p1, p2, ..., pF] #cf_span[(1 ≤ pi ≤ 109)]，表示每种花的花瓣数量。第三行包含 #cf_span[B] 个整数 #cf_span[c1, c2, ..., cB] #cf_span[(1 ≤ ci ≤ 250)]，表示每种盒子中的巧克力数量。\n\n## Output\n\n请输出 Pieguy 可以购买的花束+篮子组合数，对 #cf_span[1000000007 = 109 + 7] 取模。\n\n[samples]\n\n## Note\n\n在第一个例子中，有 #cf_span[1] 种方式制作出总花瓣数为 #cf_span[9] 的花束 #cf_span[(3 + 3 + 3)]，有 #cf_span[1] 种方式制作出总巧克力数为 #cf_span[9] 的篮子 #cf_span[(3 + 3 + 3)]，共 #cf_span[1] 种组合。有 #cf_span[3] 种方式制作出总花瓣数为 #cf_span[13] 的花束 #cf_span[(3 + 5 + 5, 5 + 3 + 5, 5 + 5 + 3)]，有 #cf_span[5] 种方式制作出总巧克力数为 #cf_span[13] 的篮子 #cf_span[(3 + 10, 10 + 3, 3 + 3 + 7, 3 + 7 + 3, 7 + 3 + 3)]，共 #cf_span[15] 种额外组合。最后，有 #cf_span[1] 种方式制作出总花瓣数为 #cf_span[15] 的花束 #cf_span[(5 + 5 + 5)]，有 #cf_span[1] 种方式制作出总巧克力数为 #cf_span[15] 的篮子 #cf_span[(3 + 3 + 3 + 3 + 3)]，共 #cf_span[1] 种组合。\n注意，多种花可能具有相同数量的花瓣，但这些类型仍被视为不同。同样，不同类型的盒子可能包含相同数量的巧克力，但它们仍被视为不同。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ F, B, N \\in \\mathbb{Z}^+ $ with $ 1 \\leq F \\leq 10 $, $ 1 \\leq B \\leq 100 $, $ 1 \\leq N \\leq 10^{18} $.  \nLet $ \\mathbf{p} = (p_1, p_2, \\dots, p_F) \\in \\mathbb{Z}^F $ be the petal counts for flower types.  \nLet $ \\mathbf{c} = (c_1, c_2, \\dots, c_B) \\in \\mathbb{Z}^B $ be the chocolate counts for box types.  \n\nLet $ \\mathcal{A} $ be the set of all ordered sequences (bouquets) of length $ N $ where each element is chosen from $ \\{1, \\dots, F\\} $, representing flower types.  \nLet $ \\mathcal{B} $ be the set of all finite ordered sequences (baskets) where each element is chosen from $ \\{1, \\dots, B\\} $, representing box types.  \n\nFor a bouquet $ A \\in \\mathcal{A} $, define its total petal count as $ \\sigma(A) = \\sum_{i=1}^N p_{A_i} $.  \nFor a basket $ B \\in \\mathcal{B} $, define its total chocolate count as $ \\tau(B) = \\sum_{j=1}^{|B|} c_{B_j} $.  \n\n**Constraints**  \n1. $ \\sigma(A) = \\tau(B) $ for a valid combination $ (A, B) $.  \n2. All computations are performed modulo $ 10^9 + 7 $.  \n\n**Objective**  \nCompute:  \n$$\n\\sum_{\\substack{A \\in \\mathcal{A} \\\\ B \\in \\mathcal{B} \\\\ \\sigma(A) = \\tau(B)}} 1 \\mod (10^9 + 7)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF866G","tags":["math"],"sample_group":[["2 3 3\n3 5\n10 3 7","17"],["6 5 10\n9 3 3 4 9 9\n9 9 1 6 4","31415926"]],"created_at":"2026-03-03 11:00:39"}}