Coin Change

locked

Problem Statement: Bademi (B) owes Pallavi (P) live in a fictional land of their own. B recently took P out for dinner. Although at that time B chivalrously paid for the meal, P is now confused and wishes to pay him back (with coins). In this strange land, coins come in denominations 1, 2, 6 and 12. Assuming that P has an infinite supply of coins, count the number of ways P can pay back B.

Input Format: A single line containing T, the number of test cases. N lines follow, each containing a number N , the amount of money P owes B.

Constraints:

1 <= T <= 100
1 <= N <= 10 ** 9

Output Format: A single line for each test case, containing the number of ways P can pay back B. Since this number can be very big, output it modulo 10^9 + 7

Sample Input:

3
1
4
125

Sample Output:

1
3
2838

  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score