Statistics

Problem Statement

You have a digital display with an infinite number of positions. Each position consists of 7 segments - 4 vertical and 3 horizontal. Lighting certain segments within a position allows you to represent different decimal digits on the display:

                   

You can use the display to represent different non-negative integers. To represent an integer you need to show its digits, in order, on consecutive display positions. The integers you represent on the display cannot have extra leading zeros.

You are given an int n, and your task is to count each integer that can be represented by lighting exactly n segments. Return this count modulo 1,000,000,007.

Definition

Class:

SegmentDisplay

Method:

howManyNumbers

Parameters:

int

Returns:

int

Method signature:

int howManyNumbers(int n)

(be sure your method is public)

Constraints

• n will be between 0 and 500000, inclusive.

Examples

1. 2

   Returns: 1

   Using 2 segments you can represent an integer 1.

2. 1

   Returns: 0

   One segment is not enough to display even one digit.

3. 6

   Returns: 7

   Using 6 segments you can represent integers 0, 6, 9, 14, 41, 77, 111.

4. 10

   Returns: 59

5. 0

   Returns: 0

6. 132

   Returns: 316551649

7. 1234

   Returns: 784891370

8. 480

   Returns: 349710798

9. 43092

   Returns: 303482407

10. 23456

    Returns: 458113089

11. 50000

    Returns: 208262111

12. 49999

    Returns: 411010332

13. 49998

    Returns: 585239692

14. 30000

    Returns: 437894589

15. 4321

    Returns: 748782060

16. 7139

    Returns: 837106957

17. 8430

    Returns: 470591483

18. 23094

    Returns: 202063093

19. 48130

    Returns: 854522348

20. 13872

    Returns: 855193772

21. 38123

    Returns: 211161181

22. 3719

    Returns: 450030610

23. 8310

    Returns: 712665333

24. 500000

    Returns: 138757250

25. 499999

    Returns: 872544874

26. 74298

    Returns: 766298829

27. 482092

    Returns: 453446804

28. 238091

    Returns: 578896893

29. 132312

    Returns: 485107853

30. 111111

    Returns: 402461183

31. 123456

    Returns: 580882242

32. 432101

    Returns: 271982362

33. 389121

    Returns: 767810115

34. 64328

    Returns: 359709827

35. 74932

    Returns: 598600155

36. 78421

    Returns: 461193820

37. 238291

    Returns: 106222222

38. 3

    Returns: 1

39. 4

    Returns: 2

40. 5

    Returns: 5

41. 7

    Returns: 12

42. 8

    Returns: 19

43. 9

    Returns: 33

44. 499999

    Returns: 872544874

45. 499998

    Returns: 59869508

46. 497997

    Returns: 874697853

47. 450000

    Returns: 187652507