FastPrep

Description

Solutions

To Good Arrays

📚RELATED PROBLEMS

You are given three integers N, M and K.

An array is said to be good if there is exactly K indices i such that A[i] * A[i + 1] is equal to M.

Find the number of good arrays A. Since the answer can be very large, return it modulo 10^9 + 7.

Input Format

The first line contains an integer, N, denoting one of the given three integers.

The next line contains an integer, M, denoting one of the three given integers.

The next line contains an integer, K, denoting one of the three given integers.

Example 1:

Input:  N = 2, M = 3, K = 0
Output: 7 
Explanation:
      
      Given N = 2, M = 3, K = 0.
      
      
      There exists 7 possible arrays A. Some of them are [3, 3] and [1, 2].

Example 2:

Input:  N = 2, M = 3, K = 1
Output: 2 
Explanation:
      
      Given N = 2, M = 3, K = 1.
      
      
      There exists only two possible arrays A which are [1, 3] and [3, 1].

Example 3:

Input:  N = 5, M = 10, K = 2
Output: 1368 
Explanation:
      
      Given N = 5, M = 10, K = 2.
      
      
      There exists a total of 1368 possible arrays A.

Constraints:

2 <= N <= 10^9
3 <= M <= 10^9
0 <= K <= min(50, N - 1)