G. Generative Model

Codeforces

IDCF10146G

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Bob is creating an algorithm that can generate words. It works as follows: Given an integer seed s: For example, if s = 3705 From B we can generate "mico" as follows: [13, 9, 3, 15 = [m, i, c, o]] From B we can also generate "kecci" as follows: [11, 5, 3, 3, 9 = [k, e, c, c, i]] Please note that when doing the words-number trailing zeroes are not allowed. For example, 02 does not correspond to b. Alice thinks that Bob's model is very poor and that in fact, it can't generate words that belongs to any language. Bob is very confident about his model, that's why he wants to write a program that given s computes how many words can be generated. As Bob knows you are training to participate on the ACM - ICPC World Finals, he wants you to write a program that counts the possible words. There will be multiple cases. Each line contains a positive integer s less than 106. For each case output the number of valid words mod 109 + 7 on a single line. ## Input There will be multiple cases. Each line contains a positive integer s less than 106. ## Output For each case output the number of valid words mod 109 + 7 on a single line. [samples]

**Definitions** Let $ s \in \mathbb{Z}^+ $ with $ s < 10^6 $. Let $ \Sigma = \{1, 2, \dots, 26\} $ represent the alphabet (A=1, B=2, ..., Z=26). A *valid word* is a sequence $ (d_1, d_2, \dots, d_k) \in \Sigma^k $ for some $ k \geq 1 $, such that: $$ s = \sum_{i=1}^{k} d_i \cdot 10^{k-i} $$ (i.e., $ s $ is the base-10 number formed by concatenating the digits $ d_1, d_2, \dots, d_k $, with no leading zeros and each $ d_i \in \Sigma $). **Constraints** 1. $ 1 \leq s < 10^6 $ 2. Each digit $ d_i \in \{1, 2, \dots, 26\} $ 3. No leading zero: $ d_1 \geq 1 $ (automatically satisfied since $ d_i \in \Sigma $) **Objective** For a given $ s $, count the number of sequences $ (d_1, \dots, d_k) \in \Sigma^k $ such that the decimal concatenation of the digits equals $ s $. Output the count modulo $ 10^9 + 7 $.

API Response (JSON)

{
  "problem": {
    "name": "G. Generative Model",
    "description": {
      "content": "Bob is creating an algorithm that can generate words. It works as follows: Given an integer seed s: For example, if s = 3705 From B we can generate \"mico\" as follows: [13, 9, 3, 15 = [m, i, c, o]] ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10146G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Bob is creating an algorithm that can generate words. It works as follows:\n\nGiven an integer seed s:\n\nFor example, if s = 3705\n\nFrom B we can generate \"mico\" as follows: [13, 9, 3, 15 = [m, i, c, o]]\n...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\mathbb{Z}^+ $ with $ s < 10^6 $.  \nLet $ \\Sigma = \\{1, 2, \\dots, 26\\} $ represent the alphabet (A=1, B=2, ..., Z=26).  \nA *valid word* is a sequence $ (d_1, d_2, \\dots, ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments