B. RGB plants

Codeforces

IDCF10106B

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

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. As 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. The 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). As 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. 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). For each test case, print a single line containing the total number of flowers in the magical garden in the nth day modulo 1000000007. ## Input 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). ## Output For each test case, print a single line containing the total number of flowers in the magical garden in the nth day modulo 1000000007. [samples]

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the number of buffaloes, each with distinct ages labeled $ 1, 2, \dots, N $. Let $ S_N $ be the set of all $ N! $ permutations of $ \{1, 2, \dots, N\} $. For 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). **Constraints** $ 1 \leq N \leq 100 $ **Objective** Compute the number of permutations $ \pi \in S_N $ such that $ \mathrm{LDS}(\pi) \notin \{3, 4\} $, modulo $ 10^9 + 7 $: $$ \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) $$

API Response (JSON)

{
  "problem": {
    "name": "B. RGB plants",
    "description": {
      "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. As we all know, the garden that surrounds farmer",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10106B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "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...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**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\\}...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments