{"raw_statement":[{"iden":"statement","content":"Farmer John has recently bought three flowers in order to plant them around his house. The flowers were of three different colors red, green and blue.\n\nAs we all know, the garden that surrounds farmer John's house is a magical garden. That means that if you plant a number of flowers in it on some day, then the number of flowers will increase in the next day.\n\nThe garden increases the number of flowers depending on the color of the flowers, that is, if you plant a red flower in a day, then it will turn into 6 flowers in the next day (1 red flower, 2 green flowers, and 3 blue flowers). If you plant a green flower in a day, then it will turn into 15 flowers in the next day (4 red flowers, 5 green flowers, and 6 blue flowers). If you plant a blue flower in a day, then it will turn into 24 flowers in the next day (7 red flowers, 8 green flowers, and 9 blue flowers).\n\nAs we have mentioned above, farmer John has three flowers (1 red flower, 1 green flower, and 1 blue flower), and he will plant them in his magical garden around his house, so the number of the flowers will increase over time. Farmer John knows that if he plants his three flowers in his magical garden, then the number of flowers will increase from day to day, so he wants to know the total number of flowers in his magical garden in the nth day.\n\nThe first line of the input is the number of test cases T (1 ≤ T ≤ 103). Each test case consists of a single line containing a single integer n (1 ≤ n ≤ 109).\n\nFor each test case, print a single line containing the total number of flowers in the magical garden in the nth day modulo 1000000007.\n\n"},{"iden":"input","content":"The first line of the input is the number of test cases T (1 ≤ T ≤ 103). Each test case consists of a single line containing a single integer n (1 ≤ n ≤ 109)."},{"iden":"output","content":"For each test case, print a single line containing the total number of flowers in the magical garden in the nth day modulo 1000000007."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of buffaloes, each with distinct ages labeled $ 1, 2, \\dots, N $.  \nLet $ S_N $ be the set of all $ N! $ permutations of $ \\{1, 2, \\dots, N\\} $.  \nFor a permutation $ \\pi \\in S_N $, define $ \\mathrm{LDS}(\\pi) $ as the length of the longest decreasing subsequence of $ \\pi $ (i.e., the maximum family size).\n\n**Constraints**  \n$ 1 \\leq N \\leq 100 $\n\n**Objective**  \nCompute the number of permutations $ \\pi \\in S_N $ such that $ \\mathrm{LDS}(\\pi) \\notin \\{3, 4\\} $, modulo $ 10^9 + 7 $:  \n$$\n\\left| \\left\\{ \\pi \\in S_N \\mid \\mathrm{LDS}(\\pi) \\neq 3 \\text{ and } \\mathrm{LDS}(\\pi) \\neq 4 \\right\\} \\right| \\mod (10^9 + 7)\n$$","simple_statement":"Count the number of permutations of N distinct buffaloes such that the longest decreasing subsequence has length not equal to 3 or 4. Print the answer modulo 10^9 + 7.","has_page_source":false}