We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #106: Special subset sums: meta-testing

Project Euler #106: Special subset sums: meta-testing

Problem
Submissions
Leaderboard
Discussions

This problem is a programming version of Problem 106 from projecteuler.net

Let represent the sum of elements in set of size . We shall call it a special sum set if for any two non-empty disjoint subsets, and , the following properties are true:

  • ; that is, sums of subsets cannot be equal.
  • If contains more elements than then .

For this problem we shall assume that a given set contains strictly increasing elements and it already satisfies the second rule.

Surprisingly, out of the possible subset pairs that can be obtained from a set for which , only of these pairs need to be tested for equality (first rule). Similarly, when , only out of the subset pairs need to be tested.

For a given set size , how many subset pairs need to be tested for equality?

Input Format

First line contains an integer denoting the number of test cases.
Each of the following lines contain one integer - the size of set.

Constraints

Output Format

For each of test cases print one line containing a single integer - the number of subset pairs that need to be tested for equality. As this number can be extremely large, output it modulo .

Sample Input

3
3
4
7

Sample Output

0
1
70

Author

bayleef

Difficulty

Easy

Max Score

100

Submitted By

244

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy