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 #137: Fibonacci golden nuggets

Project Euler #137: Fibonacci golden nuggets

Problem
Submissions
Leaderboard
Discussions

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

Consider the infinite polynomial series , where is the term in the Fibonacci sequence: ; that is, , and .

For this problem we shall be interested in values of for which is a positive integer.

Surprisingly

The corresponding values of for the first five natural numbers are shown below.

We shall call a golden nugget if is rational, because they become increasingly rarer; for example, the golden nugget is .

Given , find the golden nugget. Since this number can be very large, output it modulo .

Input Format

The first line of input contains , the number of test cases.

Each test case consists of a single line containing a single integer, .

Constraints

In the first test case:
In the second test case:
In the third test case:

Output Format

For each test case, output a single line containing a single integer, the answer for that test case.

Sample Input

2
1
10

Sample Output

2
74049690

Author

kevinsogo

Difficulty

Easy

Max Score

100

Submitted By

454

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