Data Modelling & AI Data Structure & Algorithm

Count ways to place M objects in distinct partitions of N boxes

23 June 2025

0

Given two positive integers N and M, the task is to find the number of ways to place M distinct objects in partitions of even indexed boxes which are numbered [1, N] sequentially, and every i^th Box has i distinct partitions. Since the answer can be very large, print modulo 1000000007.

Examples:

Input: N = 2, M = 1
Output: 2
Explanation: Since, N = 2. There is only one even indexed box i.e box 2, having 2 partitions. Therefore, there are two positions to place an object. Therefore, number of ways = 2.

Input: N = 5, M = 2
Output: 32

Approach: Follow the steps below to solve the problem:

M objects are to be placed in even indexed box’s partitions. Let S be the total even indexed box’s partitions in N boxes.
The number of partitions is equal to the summation of all even numbers up to N. Therefore, Sum, S = X * (X + 1), where X = floor(N / 2).
Each object can occupy one of S different positions. Therefore, the total number of ways = S*S*S..(M times) = S^M.

Below is the implementation of the above approach:

C++

// C++ implementation of the
// above Approach
 
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1000000007;
 
// Iterative Function to calculate
// (x^y)%p in O(log y)
int power(int x, unsigned int y, int p = MOD)
{
    // Initialize Result
    int res = 1;
 
    // Update x if x >= MOD
    // to avoid multiplication overflow
    x = x % p;
 
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * 1LL * x) % p;
 
        // multiplied by long long int,
        // to avoid overflow
        // because res * x <= 1e18, which is
        // out of bounds for integer
 
        // n must be even now
 
        // y = y/2
        y = y >> 1;
 
        // Change x to x^2
        x = (x * 1LL * x) % p;
    }
    return res;
}
 
// Utility function to find
// the Total Number of Ways
void totalWays(int N, int M)
{
    // Number of Even Indexed
    // Boxes
    int X = N / 2;
 
    // Number of partitions of
    // Even Indexed Boxes
    int S = (X * 1LL * (X + 1)) % MOD;
 
    // Number of ways to distribute
    // objects
    cout << power(S, M, MOD) << "\n";
}
 
// Driver Code
int main()
{
    // N = number of boxes
    // M = number of distinct objects
    int N = 5, M = 2;
 
    // Function call to
    // get Total Number of Ways
    totalWays(N, M);
 
    return 0;
}

Java

// Java implementation of the
// above Approach
import java.io.*;
class GFG
{
   
public static int MOD = 1000000007;
 
// Iterative Function to calculate
// (x^y)%p in O(log y)
static int power(int x, int y, int p)
{    
      p = MOD;
   
    // Initialize Result
    int res = 1;
 
    // Update x if x >= MOD
    // to avoid multiplication overflow
    x = x % p;
 
    while (y > 0) 
    {
 
        // If y is odd, multiply x with result
        if ((y & 1) != 0)
            res = (res * x) % p;
 
        // multiplied by long long int,
        // to avoid overflow
        // because res * x <= 1e18, which is
        // out of bounds for integer
 
        // n must be even now
 
        // y = y/2
        y = y >> 1;
 
        // Change x to x^2
        x = (x * x) % p;
    }
    return res;
}
 
// Utility function to find
// the Total Number of Ways
static void totalWays(int N, int M)
{
   
    // Number of Even Indexed
    // Boxes
    int X = N / 2;
 
    // Number of partitions of
    // Even Indexed Boxes
    int S = (X * (X + 1)) % MOD;
 
    // Number of ways to distribute
    // objects
    System.out.println(power(S, M, MOD));
}
 
// Driver Code
public static void main (String[] args) 
{
     
      // N = number of boxes
    // M = number of distinct objects
    int N = 5, M = 2;
 
    // Function call to
    // get Total Number of Ways
    totalWays(N, M);
}
}
 
// This code is contributed by Dharanendra L V

Python3

# Python3 implementation of the
# above Approach
MOD = 1000000007
 
# Iterative Function to calculate
# (x^y)%p in O(log y)
def power(x, y, p = MOD):
   
    # Initialize Result
    res = 1
 
    # Update x if x >= MOD
    # to avoid multiplication overflow
    x = x % p
    while (y > 0):
 
        # If y is odd, multiply x with result
        if (y & 1):
            res = (res * x) % p
 
        # multiplied by long long int,
        # to avoid overflow
        # because res * x <= 1e18, which is
        # out of bounds for integer
 
        # n must be even now
 
        # y = y/2
        y = y >> 1
 
        # Change x to x^2
        x = (x * x) % p
    return res
 
# Utility function to find
# the Total Number of Ways
def totalWays(N, M):
   
    # Number of Even Indexed
    # Boxes
    X = N // 2
 
    # Number of partitions of
    # Even Indexed Boxes
    S = (X * (X + 1)) % MOD
 
    # Number of ways to distribute
    # objects
    print (power(S, M, MOD))
 
# Driver Code
if __name__ == '__main__':
 
    # N = number of boxes
    # M = number of distinct objects
    N, M = 5, 2
 
    # Function call to
    # get Total Number of Ways
    totalWays(N, M)
 
# This code is contributed by mohit kumar 29.

C#

// C# implementation of the
// above Approach
 
using System;
 
public class GFG{
 
public static int MOD = 1000000007;
 
// Iterative Function to calculate
// (x^y)%p in O(log y)
static int power(int x, int y, int p)
{
       
      p = MOD;
   
    // Initialize Result
    int res = 1;
 
    // Update x if x >= MOD
    // to avoid multiplication overflow
    x = x % p;
 
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if ((y & 1) != 0)
            res = (res * x) % p;
 
        // multiplied by long long int,
        // to avoid overflow
        // because res * x <= 1e18, which is
        // out of bounds for integer
 
        // n must be even now
 
        // y = y/2
        y = y >> 1;
 
        // Change x to x^2
        x = (x * x) % p;
    }
    return res;
}
 
// Utility function to find
// the Total Number of Ways
static void totalWays(int N, int M)
{
   
    // Number of Even Indexed
    // Boxes
    int X = N / 2;
 
    // Number of partitions of
    // Even Indexed Boxes
    int S = (X * (X + 1)) % MOD;
 
    // Number of ways to distribute
    // objects
    Console.WriteLine(power(S, M, MOD));
}
 
// Driver Code
static public void Main ()
{
 
    // N = number of boxes
    // M = number of distinct objects
    int N = 5, M = 2;
 
    // Function call to
    // get Total Number of Ways
    totalWays(N, M);
}
}
 
// This code is contributed by Dharanendra L V

Javascript

<script>
 
// Javascript implementation of the
// above Approach
 
var MOD = 1000000007;
 
// Iterative Function to calculate
// (x^y)%p in O(log y)
function power(x, y, p = MOD)
{
    // Initialize Result
    var res = 1;
 
    // Update x if x >= MOD
    // to avoid multiplication overflow
    x = x % p;
 
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * 1 * x) % p;
 
        // multiplied by long long int,
        // to avoid overflow
        // because res * x <= 1e18, which is
        // out of bounds for integer
 
        // n must be even now
 
        // y = y/2
        y = y >> 1;
 
        // Change x to x^2
        x = (x * 1 * x) % p;
    }
    return res;
}
 
// Utility function to find
// the Total Number of Ways
function totalWays(N, M)
{
    // Number of Even Indexed
    // Boxes
    var X = parseInt(N / 2);
 
    // Number of partitions of
    // Even Indexed Boxes
    var S = (X * 1 * (X + 1)) % MOD;
 
    // Number of ways to distribute
    // objects
    document.write( power(S, M, MOD) << "<br>");
}
 
// Driver Code
// N = number of boxes
// M = number of distinct objects
var N = 5, M = 2;
// Function call to
// get Total Number of Ways
totalWays(N, M);
 
</script>

Output:

Time Complexity: O(log M)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

3 COMMENTS

sultangeymskz.sbs 20 February 2026 At 6:36 pm

… [Trackback]

[…] Find More to that Topic: geeksforgeeks.org/count-ways-to-place-m-objects-in-distinct-partitions-of-n-boxes/ […]

Log in to leave a comment
https://izzi--official.timesecret.ru/ 12 May 2026 At 2:17 am

… [Trackback]

[…] Find More on on that Topic: geeksforgeeks.org/count-ways-to-place-m-objects-in-distinct-partitions-of-n-boxes/ […]

Log in to leave a comment
https://ice-fishing-casino-demo.kz/ru-kz/ 21 May 2026 At 7:50 pm

… [Trackback]

[…] Info on that Topic: geeksforgeeks.org/count-ways-to-place-m-objects-in-distinct-partitions-of-n-boxes/ […]

Log in to leave a comment

Count ways to place M objects in distinct partitions of N boxes

C++

Java

Python3

C#

Javascript

Adding Persistent Memory to Claude Code with the Lightweight memsearch Plugin

GLM-5 vs. MiniMax M2.5 vs. Gemini 3 Deep Think: Which Model Fits Your AI Agent Stack?

We Extracted OpenClaw’s Memory System and Open-Sourced It (memsearch)

3 COMMENTS

LEAVE A REPLY Cancel reply

Most Popular

The Galaxy Watch 9 raises the bar for Wear OS updates

The Pixel Watch 5 could carry forward its biggest weakness

Google has bet the house on the Pixel 11. [Video]

You should be excited right now. [Video]

EDITOR PICKS

The Galaxy Watch 9 raises the bar for Wear OS updates

The Pixel Watch 5 could carry forward its biggest weakness

Google has bet the house on the Pixel 11. [Video]

POPULAR POSTS

The Galaxy Watch 9 raises the bar for Wear OS updates

The Pixel Watch 5 could carry forward its biggest weakness

Google has bet the house on the Pixel 11. [Video]

POPULAR CATEGORY

ABOUT US

FOLLOW US