```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	fib []int64
	D   []int64
)

const MOD int64 = 1e9 + 7

func initFib() {
	fib = make([]int64, 0, 90)
	fib = append(fib, 1, 2)
	for i := 2; ; i++ {
		next := fib[i-1] + fib[i-2]
		if next > 1e18 {
			break
		}
		fib = append(fib, next)
	}

	D = make([]int64, len(fib)+2)
	D[0] = 1 
	D[1] = 1 
	for i := 2; i < len(D); i++ {
		D[i] = (D[i-1] + D[i-2]) % MOD
	}
}

func solve(n int64) int64 {
	indices := make([]int, 0)
	for i := len(fib) - 1; i >= 0; i-- {
		if fib[i] <= n {
			indices = append(indices, i)
			n -= fib[i]
		}
	}

	if len(indices) == 0 {
		return 1
	}

	dp0 := int64(1)
	dp1 := int64(0)

	for i := 0; i < len(indices); i++ {
		u := indices[i]
		var v int
		if i == len(indices)-1 {
			v = -2 
		} else {
			v = indices[i+1]
		}

		gap := u - v
		
		var wSafe, wUnsafe int64
		
		if gap == 1 {
			wSafe = 0
			wUnsafe = 1
		} else {
			wSafe = D[u-2] - 1
			if wSafe < 0 {
				wSafe += MOD
			}
			wUnsafe = 1
		}
		
		if gap == 1 {
			wSafe = 0 
		} else {
			wSafe = D[u-2] - 1
			if wSafe < 0 {
				wSafe += MOD
			}
		}
		
		if gap == 1 {
			wUnsafe = 1
		} else {
			wUnsafe = 1
		}
		
		if gap == 1 {
			wSafe = 0
		} else {
			wSafe = D[u-2] - 1
			if wSafe < 0 {
				wSafe += MOD
			}
		}
		wUnsafe = 1
		
		ndp0 := (dp0 + wSafe*dp0 + wUnsafe*dp1) % MOD
		ndp1 := (wSafe*dp0 + wUnsafe*dp1) % MOD
		
		if gap == 1 {
			ndp0 = dp1
			ndp1 = dp1
		} else {
			wSafe := D[u-2] - 1
			if wSafe < 0 {
				wSafe += MOD
			}
			ndp0 = (dp0 + wSafe*dp0 + dp1) % MOD
			ndp1 = (wSafe*dp0 + dp1) % MOD
		}
		
		dp0 = ndp0
		dp1 = ndp1
	}

	return dp0
}

func main() {
	initFib()

	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var t int
	fmt.Fscan(reader, &t)

	for i := 0; i < t; i++ {
		var n int64
		fmt.Fscan(reader, &n)
		fmt.Fprintln(writer, solve(n))
	}
}
```