Statistics

Problem Statement for "NineEasy"

Problem Statement

Bob's little sister Alice is nine years old. Bob is testing her mathematical prowess by asking her to compute the remainder a number gives when divided by 9.

Today, Bob gave Alice exactly N such questions. We will number the questions 0 through N-1. In each question, Bob gave Alice the same M-digit number. (Note that Bob's number is allowed to have some leading zeros.)

In some of those cases Alice may have skipped some of the digits when reading the number. However, she never made any other mistakes in her calculations For example, if Bob gave Alice the number 012345 three times, she may have read it as 0145 the first time, 012345 the second time, and 135 the third time. Then, her answers would be 145 modulo 9 = 1, 12345 modulo 9 = 6, and 135 modulo 9 = 0.

You are given the int N and a int[] d with M elements. For each i, the number d[i] corresponds to the digit of the order 10^i in Bob's number. For each i and j, Alice read digit i when answering question j if and only if bit number j of the number d[i] is 1.

For example, suppose that d[3] = 6. In binary, 6 is 110. In other words, the binary digits number 0, 1, and 2 are 0, 1, and 1. Hence, Alice skipped the corresponding digit in question 0 but she read it in questions 1 and 2.

A surprising thing happened in today's experiment: For each of the N questions, Alice's answer was that the remainder is 0. Bob found that interesting. He now wonders: given N and d, how many different M-digit numbers have this property?

Let X be the answer to Bob's question. Compute and return the value (X modulo 1,000,000,007).

Definition

Class:
NineEasy
Method:
count
Parameters:
int, int[]
Returns:
int
Method signature:
int count(int N, int[] d)
(be sure your method is public)

Constraints

  • N will be between 1 and 5, inclusive.
  • The number of elements in d will be between 1 and 20, inclusive.
  • All elements in d must be between 0 and 2N-1, inclusive
  • d will be such that in each question Alice will read at least one digit.

Examples

  1. 2

    {1,2}

    Returns: 4

    In this case we have N=2 questions and Bob's number has two digits. When processing question 0, Alice only reads digit 0 (the last digit of the number). As her answer is that the remainder is 0, this digit must be either 0 or 9. When processing question 1, Alice only reads digit 1 (the first digit of the number). As her answer is that the remainder is 0 again, this digit must also be either 0 or 9. Thus there are four possible numbers: 00, 09, 90, and 99.

  2. 2

    {3,3}

    Returns: 12

    Again, we have N=2 questions and Bob's number has two digits. This time Alice in each question reads both digits. Thus the only information we have is that Bob's entire number is divisible by 9. There are 12 such numbers: 00, 09, 18, 27, ..., 90, and 99.

  3. 2

    {1,3,2}

    Returns: 16

  4. 5

    {1,2,4,8,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31}

    Returns: 893703876

  5. 1

    {0,0,1}

    Returns: 200

  6. 1

    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 333333881

  7. 5

    {31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31}

    Returns: 333333881

  8. 5

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,31}

    Returns: 980

  9. 4

    {15}

    Returns: 2

  10. 1

    {0,1,1,1,0,0,1,1,0,0,0,1,0,1,1,0,0,0,0,1}

    Returns: 222222146

  11. 1

    {1,1,1,1,0,1,1,0,0,1,1,1,1,0,0,0,0,0,0,0}

    Returns: 222222706

  12. 1

    {0,0,1,1,1,0,1,0,1,0,1,1,1,0,0,0,1,0,0,0}

    Returns: 222222146

  13. 2

    {3,2,1,0,3,1,3,2,0,3,1,3,1,2,0,3,0,0,1,2}

    Returns: 555624679

  14. 2

    {1,2,3,0,3,3,3,2,2,3,1,1,2,1,1,0,3,0,1,3}

    Returns: 680000749

  15. 2

    {2,1,3,0,3,0,2,3,1,3,1,0,0,3,2,3,3,1,1,1}

    Returns: 457784679

  16. 3

    {5,0,7,4,3,6,7,5,4,6,4,0,6,7,7,4,5,0,2,1}

    Returns: 664452425

  17. 3

    {5,7,7,6,0,1,2,7,5,0,0,6,1,6,6,2,1,0,6,2}

    Returns: 470183551

  18. 3

    {4,2,5,2,2,7,3,1,2,3,5,4,3,4,7,6,3,2,0,3}

    Returns: 580336766

  19. 4

    {4,5,8,13,11,3,5,1,10,3,4,9,0,15,4,5,2,0,4,5}

    Returns: 109306378

  20. 4

    {1,14,6,6,3,0,10,8,12,5,1,5,0,4,13,5,14,14,12,13}

    Returns: 138351351

  21. 4

    {10,15,10,0,10,6,0,8,4,7,11,4,3,1,5,15,3,2,7,8}

    Returns: 252780751

  22. 5

    {27,15,6,20,8,2,1,28,15,18,20,20,27,13,5,12,28,0,30,17}

    Returns: 176267203

  23. 5

    {21,4,19,21,29,17,19,9,25,25,26,20,29,16,9,17,13,12,9,1}

    Returns: 894308276

  24. 5

    {31,5,0,5,16,31,27,8,27,24,25,0,18,1,19,24,25,3,2,10}

    Returns: 341103193

  25. 5

    {25,25,28,24,0,15,28,11,29,29,31,25,7,16,31,0,12,26,21,31}

    Returns: 288393436

  26. 5

    {25,4,12,29,19,14,9,27,22,5,5,5,6,24,22,13,31,12,4,29}

    Returns: 267686778

  27. 5

    {28,7,16,8,19,11,4,25,29,31,28,5,15,22,10,22,8,0,17,16}

    Returns: 508700670

  28. 5

    {3,18,4,15,12,0,24,7,9,31,2,6,11,20,10,23,31,30,28,24}

    Returns: 828910486

  29. 5

    {4,13,19,15,3,24,26,15,11,22,12,30,5,1,8,19,28,0,4,4}

    Returns: 978991294

  30. 5

    {20,8,24,11,19,12,18,11,14,0,18,28,13,30,6,25,3,25,7,10}

    Returns: 268192997

  31. 5

    {12,8,7,28,23,27,1,7,27,29,31,9,25,0,10,3,17,7,8,7}

    Returns: 887700065

  32. 5

    {22,9,3,0,21,17,24,14,15,13,4,12,22,15,31,1,29,25,13,18}

    Returns: 85615536

  33. 5

    {8,18,31,17,28,11,0,15,24,19,18,25,17,24,5,5,8,2,2,26}

    Returns: 308348974

  34. 5

    {5,0,18,25,24,31,7,29,31,6,31,15,10,0,27,24,23,29,19,28}

    Returns: 346242919

  35. 5

    {2,30,20,9,30,23,2,3,18,15,19,4,22,9,25,18,15,12,30,26}

    Returns: 774720374

  36. 5

    {3,0,4,25,18,31,14,20,15,7,28,19,26,18,21,23,18,14,2,0}

    Returns: 77966416

  37. 5

    {5,26,27,23,28,10,10,31,16,14,5,30,30,26,23,2,19,27,0,1}

    Returns: 626829947

  38. 5

    {23,23,28,10,18,17,16,21,17,28,22,26,1,3,27,26,25,25,25,27}

    Returns: 885677707

  39. 5

    {11,18,1,18,6,3,27,8,13,12,8,29,31,10,14,27,0,12,0,30}

    Returns: 972417918

  40. 5

    {12,2,21,21,25,26,25,4,14,20,10,0,24,4,1,4,3,7,3,19}

    Returns: 759086689

  41. 5

    {0,20,8,29,6,7,11,25,11,20,24,17,3,14,26,9,7,7,16,12}

    Returns: 778939970

  42. 5

    {18,20,3,28,24,21,18,14,16,17,24,3,14,24,24,10,14,25,30,5}

    Returns: 300316258

  43. 5

    {19,5,16,3,8,25,4,14,14,17,28,26,12,5,13,5,5,0,16,15}

    Returns: 861848698

  44. 5

    {22,0,16,12,2,30,2,18,9,1,15,24,26,7,13,6,1,1,19,6}

    Returns: 290215468

  45. 5

    {15,30,25,19,13,10,25,13,31,15,29,4,12,0,14,4,10,10,6,27}

    Returns: 781832384

  46. 5

    {2,3,19,21,13,19,12,8,21,17,12,3,21,25,6,24,28,15,25,11}

    Returns: 719721769

  47. 5

    {17,31,11,5,13,1,20,27,30,22,24,10,8,21,14,15,4,15,0,18}

    Returns: 358783912

  48. 5

    {6,21,25,1,17,8,16,13,28,1,14,2,13,29,25,3,30,3,22,2}

    Returns: 814842248

  49. 5

    {12,13,20,0,27,5,23,30,22,10,31,18,6,27,22,30,31,7,12,14}

    Returns: 504587632

  50. 5

    {9,26,8,0,11,4,13,5,28,18,2,13,21,31,11,8,28,4,22,4}

    Returns: 607658997

  51. 5

    {16,11,24,14,3,19,10,4,17,0,27,28,24,25,29,20,20,20,22,19}

    Returns: 975150026

  52. 2

    {1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2}

    Returns: 567901286

  53. 5

    {1, 2, 4, 8, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 }

    Returns: 893703876

  54. 2

    {1, 3, 2 }

    Returns: 16

  55. 1

    {0, 0, 1 }

    Returns: 200

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: