Statistics

Problem Statement for "LittleElephantAndSubset"

Problem Statement

Little Elephant from the Zoo of Lviv has a set S. The set S contains the integers 1, 2, 3, ..., N. He considers some non-empty subset of S cool if we can write down all elements of the subset by using each of the digits 0-9 at most once.

Examples: The subsets {12,345,67890} and {47,109} are cool. The subset {147,342} is not cool because the digit 4 is used twice. The subset {404} is not cool for the same reason.

You are given the int N. Let X be the total number of non-empty cool subsets of S. Return the value (X modulo 1,000,000,007).

Definition

Class:
LittleElephantAndSubset
Method:
getNumber
Parameters:
int
Returns:
int
Method signature:
int getNumber(int N)
(be sure your method is public)

Constraints

  • N will be between 1 and 1,000,000,000 (10^9), inclusive.

Examples

  1. 3

    Returns: 7

    All 7 non-empty subsets are cool in this case: {1, 2, 3} {1, 2} {1, 3} {2, 3} {1} {2} {3}

  2. 10

    Returns: 767

    In this case, the total number of non-empty subsets is 2^10-1 = 1023. The only not cool subsets are those that contain both 1 and 10. There are 2^8 = 256 of them. Thus, the answer is 1023-256 = 767.

  3. 47

    Returns: 25775

  4. 4777447

    Returns: 66437071

  5. 1000000000

    Returns: 88291951

  6. 1

    Returns: 1

  7. 7

    Returns: 127

  8. 999999999

    Returns: 88291951

  9. 100000001

    Returns: 82122991

  10. 777777777

    Returns: 86769871

  11. 474747474

    Returns: 84676111

  12. 883

    Returns: 5821431

  13. 153

    Returns: 613623

  14. 222

    Returns: 844479

  15. 893

    Returns: 5895791

  16. 234

    Returns: 861303

  17. 428

    Returns: 1821447

  18. 651

    Returns: 3447559

  19. 24866

    Returns: 27503839

  20. 61390

    Returns: 35897155

  21. 6619

    Returns: 17076727

  22. 78830

    Returns: 39888079

  23. 84077

    Returns: 41330863

  24. 42098

    Returns: 31520311

  25. 1658

    Returns: 8228067

  26. 1200147

    Returns: 61613551

  27. 1777734

    Returns: 62445391

  28. 9818267

    Returns: 73308751

  29. 8012510

    Returns: 70753791

  30. 8351202

    Returns: 71294471

  31. 618985

    Returns: 54575911

  32. 3988088

    Returns: 65430511

  33. 783837108

    Returns: 86806711

  34. 349651100

    Returns: 83798083

  35. 683484993

    Returns: 86118415

  36. 553337439

    Returns: 85247791

  37. 88068199

    Returns: 81049471

  38. 972282891

    Returns: 88162951

  39. 781586125

    Returns: 86786455

  40. 258626540

    Returns: 83178607

  41. 246182120

    Returns: 83080807

  42. 762952004

    Returns: 86722729

  43. 918195326

    Returns: 87754831

  44. 258677230

    Returns: 83179213

  45. 419698256

    Returns: 84332911

  46. 491250840

    Returns: 84801167

  47. 19

    Returns: 1791

  48. 1000000

    Returns: 61438831

  49. 13

    Returns: 1023

  50. 100000000

    Returns: 82122991

  51. 14

    Returns: 1151

  52. 999999998

    Returns: 88291951

  53. 907014377

    Returns: 87666991

  54. 16

    Returns: 1407

  55. 713526152

    Returns: 86340133

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: