Statistics

Problem Statement for "OrderedProduct"

Problem Statement

Let p[] be an infinite array containing all prime numbers in ascending order. That is, p[0]=2, p[1]=3, p[2]=5, p[3]=7, and so on.

You are given a int[] a. Each a[i] is the exponent of the prime p[i] in the factorization of a large number X. Formally, X = p[0]^a[0] * p[1]^a[1] * ... * p[n-1]^a[n-1], where n is the number of elements of a.

Compute the number of sequences of positive integers such that each integer is greater than 1 and the product of all elements of the sequence is exactly X. Return that number modulo 1,000,000,007.

Definition

Class:
OrderedProduct
Method:
count
Parameters:
int[]
Returns:
int
Method signature:
int count(int[] a)
(be sure your method is public)

Constraints

  • a will contain between 1 and 50 elements, inclusive.
  • Each element of a will be between 1 and 50, inclusive.

Examples

  1. {1, 1}

    Returns: 3

    Here, X = 2^1 * 3^1 = 6. There are three valid sequences: (2,3), (3,2), and (6).

  2. {2}

    Returns: 2

    We have X = 2^2 = 4. The two valid sequences are (2,2) and (4).

  3. {1, 1, 1, 1, 1}

    Returns: 541

  4. {23, 49, 12}

    Returns: 316396073

    Watch out for integer overflow.

  5. {2, 5, 4, 2, 3, 1, 3, 1, 4, 6}

    Returns: 225466557

  6. {4, 10, 5}

    Returns: 194031603

  7. {1, 1, 1, 1, 1}

    Returns: 541

  8. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: 569760615

  9. {1, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1}

    Returns: 153766160

  10. {4, 4, 4, 4, 4, 4, 4, 2, 3, 2, 1, 4, 2, 1, 4, 1, 4, 4, 1, 1, 1, 2, 1, 2, 2, 1, 4, 2, 3, 2, 4, 3, 2, 2, 4, 1, 1, 4, 2, 4, 4, 1, 2, 3, 1, 3, 1, 2, 2, 3}

    Returns: 70679862

  11. {25, 24, 19, 28, 24, 10, 14, 25, 20, 27, 22, 22, 19, 26, 28, 16, 19, 22, 22, 24, 25, 12, 24, 8, 19, 26, 4, 7, 19, 17, 2, 29, 11, 1, 23, 20, 11, 7, 24, 28, 18, 15, 10, 14, 16, 16, 26, 26}

    Returns: 589786212

  12. {6, 25, 17, 14, 21, 18, 1, 15, 13, 4, 17, 7, 15, 17, 10, 22, 19, 13, 12, 1, 3, 15, 25, 24, 3, 11, 19, 25, 13, 4, 22, 1, 5, 8, 6, 12, 15, 9, 17, 16, 2}

    Returns: 529772829

  13. {9, 9, 1, 26, 14, 7, 3, 10, 4, 6, 15, 20, 32, 1, 16, 21, 30, 24, 18, 17, 29, 15, 5, 13, 1, 16, 1, 19, 16, 5, 28, 17, 22, 31, 21, 26, 1, 18, 13, 3, 5, 22}

    Returns: 568940188

  14. {26, 4, 4, 12, 4, 20, 8, 1, 15, 9, 9, 16, 6, 32, 23, 9, 22, 20, 32, 6, 9, 23, 22, 33, 33, 12, 22, 18, 13, 33, 10, 17, 23, 30, 23, 18, 28, 18, 33, 31, 10, 27, 31}

    Returns: 721775360

  15. {38, 12, 42, 18, 47, 4, 17, 1, 8, 28, 9, 28, 9, 1, 35, 6, 15, 31, 18, 15, 47, 44, 1, 6, 8, 12, 45, 38, 9, 23, 40, 3, 36, 49, 28, 30, 14, 30, 28, 49, 35, 20, 29, 9, 2, 44, 2, 16, 33, 20}

    Returns: 585011819

  16. {27, 5, 41, 21, 37, 42, 47, 38, 37, 29, 33, 31, 41, 39, 46, 45, 31, 23, 12, 15, 20, 23, 32, 38, 39, 44, 44, 25, 12, 30, 32, 35, 45, 44, 29, 40, 50, 32, 32, 40, 8, 39, 26, 29, 12, 48, 19, 49, 37, 37}

    Returns: 255680854

  17. {36, 39, 30, 47, 49, 48, 50, 45, 42, 45, 35, 45, 48, 34, 50, 42, 9, 38, 47, 43, 49, 48, 37, 48, 50, 38, 39, 23, 41, 44, 49, 50, 44, 46, 42, 41, 45, 49, 25, 50, 37, 48, 50, 36, 47, 39, 46, 48, 49, 35}

    Returns: 240231250

  18. {36, 50, 39, 48, 49, 21, 45, 26, 30, 34, 49, 46, 32, 46, 50, 37, 31, 46, 46, 46, 42, 50, 37, 44, 48, 29, 46, 30, 43, 40, 46, 44, 36, 42, 46, 50, 39, 49, 41, 47, 43, 43, 27, 43, 30, 20, 45, 45, 41, 43}

    Returns: 545065975

  19. {50, 50, 50, 44, 44, 47, 44, 44, 44, 49, 39, 46, 45, 38, 43, 49, 46, 28, 48, 40, 45, 34, 41, 49, 36, 33, 43, 44, 49, 37, 41, 45, 35, 28, 47, 50, 46, 49, 50, 41, 46, 34, 40, 34, 41, 50, 31, 45, 43, 21}

    Returns: 990230891

  20. {49, 34, 49, 50, 48, 42, 39, 31, 37, 50, 44, 50, 49, 48, 41, 41, 44, 46, 43, 46, 42, 43, 48, 33, 35, 34, 45, 48, 50, 50, 40, 49, 42, 45, 46, 42, 50, 50, 40, 45, 48, 45, 44, 49, 41, 35, 48, 47, 38, 47}

    Returns: 654815711

  21. {49, 38, 43, 48, 25, 48, 48, 31, 50, 43, 49, 49, 34, 36, 48, 47, 42, 49, 50, 50, 46, 38, 50, 49, 44, 43, 37, 41, 50, 33, 41, 46, 45, 48, 48, 31, 44, 50, 47, 49, 45, 49, 44, 50, 49, 45, 37, 43, 48, 48}

    Returns: 909024141

  22. {47, 30, 35, 49, 44, 49, 46, 47, 50, 39, 50, 44, 45, 49, 47, 46, 40, 48, 48, 50, 43, 42, 46, 39, 49, 37, 43, 50, 48, 50, 47, 49, 50, 42, 41, 49, 50, 48, 48, 43, 48, 49, 47, 48, 45, 46, 27, 44, 47, 49}

    Returns: 908908350

  23. {48, 50, 43, 46, 50, 33, 50, 48, 40, 50, 42, 49, 50, 36, 41, 47, 50, 37, 48, 42, 49, 46, 48, 49, 44, 39, 44, 48, 47, 48, 50, 50, 49, 50, 50, 48, 48, 37, 39, 50, 45, 38, 50, 25, 47, 48, 44, 39, 43, 46}

    Returns: 369563811

  24. {2 }

    Returns: 2

  25. {2, 5, 4, 2, 3, 1, 3, 1, 4, 6 }

    Returns: 225466557

  26. {50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50 }

    Returns: 994940157

  27. {47, 45, 41, 47, 44, 42, 43, 41, 45, 46, 41, 44, 41, 46, 45, 41, 40, 49, 40, 41, 41, 41, 46, 42, 41, 45, 41, 49, 41, 40, 42, 40, 45, 45, 48, 41, 48, 41, 42, 43, 47, 44, 49, 49, 42, 44, 42, 43, 44, 43 }

    Returns: 589080495

  28. {50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50 }

    Returns: 802922726

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: