G. Repeat it

Codeforces

IDCF10106G

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Jad has bought a new computer, a really weird computer!! Every time he copies some number from the screen and pastes it, the computer pastes it many times instead of once! Jad tested his computer many times, and now he knows how many times the computer will paste each copied number. For example, In case the new computer repeated each copied number 4 times. When Jad copies the number 31 and pastes it, the number that appears on the screen would be 31313131. Given N the number that Jad copied, and M the number of times the new computer is pasting each copied number. you have to print the number that will appear on the screen. Since the number might be very big, you are asked to print it modulo 1000000007. The first line of the input consists of a single integer t, the number of test cases. Each test case consists of two numbers M and N separated by a single space: (1 ≤ M ≤ 109) is the number of times the new computer pasted the number N. (0 ≤ N ≤ 109) is the number Jad had copied. For each test case print one line, the number that will appear on the screen modulo 1000000007. ## Input The first line of the input consists of a single integer t, the number of test cases. Each test case consists of two numbers M and N separated by a single space: (1 ≤ M ≤ 109) is the number of times the new computer pasted the number N. (0 ≤ N ≤ 109) is the number Jad had copied. ## Output For each test case print one line, the number that will appear on the screen modulo 1000000007. [samples]

**Definitions** Let $ Q \in \mathbb{Z} $ be the number of queries. Let $ D_k $ be the document version at step $ k $, with $ D_0 = \emptyset $. Each document $ D_k $ is a sequence of integers (sentences), ordered from beginning to end. **Constraints** 1. $ 1 \le Q \le 10^5 $ 2. Each query is one of the following: - **A x**: Append integer $ x $ to the end of $ D_{k-1} $, resulting in $ D_k $. - **E**: Remove the first sentence from $ D_{k-1} $, resulting in $ D_k $. - **C**: Copy $ D_{k-1} $ to create $ D_k $ (no change to content). **Objective** For each query of type **E**, output the integer removed from the beginning of the document. For all other queries, update the document state accordingly. The document version index $ k $ increments by 1 after each query.

API Response (JSON)

{
  "problem": {
    "name": "G. Repeat it",
    "description": {
      "content": "Jad has bought a new computer, a really weird computer!! Every time he copies some number from the screen and pastes it, the computer pastes it many times instead of once! Jad tested his computer ma",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10106G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Jad has bought a new computer, a really weird computer!!\n\nEvery time he copies some number from the screen and pastes it, the computer pastes it many times instead of once!\n\nJad tested his computer ma...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ Q \\in \\mathbb{Z} $ be the number of queries.  \nLet $ D_k $ be the document version at step $ k $, with $ D_0 = \\emptyset $.  \nEach document $ D_k $ is a sequence of integers (s...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments