Statistics

Problem Statement for "LittleElephantAndArray"

Problem Statement

Little Elephant from the Zoo of Lviv likes sequences of integers.

You are given a long A and an int N. Little Elephant has the sequence S = (A, A+1, ..., A+N). Little Elephant now wants to erase some digits from some of the numbers. He may erase multiple digits from the same number, but he will not erase any of the numbers completely. After erasing some digits from a number the gaps disappear. For example, by erasing the middle digit of the number 147 Little Elephant obtains the number 17 (and not two separate numbers 1 and 7).

It is allowed for some number to contain leading zeroes after erasings. For example, from the number 1047 Little Elephant may create, among other possibilities, the number 047 or the number 47. These are two different ways of erasing. They are both allowed and the numbers they produce have the same value.

Two ways of erasing the digits are considered different if there is some position in some element of S that was erased in one of the cases and was not erased in the other one. For example, if S = (11, 12), there are two different ways to change it to (1, 2). (In one of them we erase the first and in the other we erase the second digit of the number 11.)

After erasing the digits, Little Elephant wants to obtain a non-decreasing sequence. Let R be the number of different ways to do that. Return R modulo 1,000,000,007.

Definition

Class:
LittleElephantAndArray
Method:
getNumber
Parameters:
long, int
Returns:
int
Method signature:
int getNumber(long A, int N)
(be sure your method is public)

Constraints

  • A will be between 1 and 1,000,000,000,000,000 (10^15), inclusive.
  • N will be between 0 and 100, inclusive.

Examples

  1. 1

    9

    Returns: 1

  2. 10

    2

    Returns: 15

  3. 4747774

    1

    Returns: 8369

  4. 6878542150015

    74

    Returns: 977836619

  5. 1000000000000000

    100

    Returns: 22435455

  6. 458975015421547

    100

    Returns: 959658342

  7. 1

    0

    Returns: 1

  8. 7

    100

    Returns: 1

  9. 4584

    99

    Returns: 723792987

  10. 698458458

    47

    Returns: 865110940

  11. 999999

    100

    Returns: 832160019

  12. 999999999999999

    99

    Returns: 726682887

  13. 999999999999

    1

    Returns: 9736590

  14. 174094882455171

    47

    Returns: 820811374

  15. 152761423221685

    99

    Returns: 626576399

  16. 761892795431233

    99

    Returns: 3096955

  17. 411387427793198

    100

    Returns: 380569836

  18. 650286024865090

    100

    Returns: 297459252

  19. 61389344606618

    100

    Returns: 966356191

  20. 49637882913598

    100

    Returns: 196396154

  21. 4

    100

    Returns: 1

  22. 76361542097372

    0

    Returns: 16383

  23. 601657541200146

    7

    Returns: 937030068

  24. 71777733599818

    2

    Returns: 109835302

  25. 266038012509478

    1

    Returns: 536875419

  26. 351201640618984

    25

    Returns: 801343434

  27. 143988087783837

    97

    Returns: 234890512

  28. 107349651099683

    100

    Returns: 476141741

  29. 4849925

    74

    Returns: 236923574

  30. 53337438088

    79

    Returns: 751395306

  31. 6819897228

    100

    Returns: 684345262

  32. 28907815861

    100

    Returns: 175903871

  33. 24258626539

    99

    Returns: 649350618

  34. 24618211976

    98

    Returns: 762873461

  35. 295200391819

    100

    Returns: 573358811

  36. 5325258677229

    100

    Returns: 184495288

  37. 4196982554

    100

    Returns: 279812471

  38. 9125083

    75

    Returns: 569602429

  39. 99999875099999

    100

    Returns: 181093175

  40. 1000000000000000

    2

    Returns: 734978268

  41. 687852150022153

    87

    Returns: 603846919

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: