Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Problem D:
IkaNumber

  数直線上の整数座標に, ねこの Taro の家, にんじん, うさぎの Hanako の家がこの順に並んでいる. 点 $x$ にいるイカは, 一回のジャンプで $x + 1$ または $x + 2$ に移動することができる.

あなたは, イカが Taro の家から Hanako の家までにんじんの置かれている座標に止まらずに行く経路が何通りあるか求めようとしたが, Taro の家, にんじん, Hanako の家の座標を知らないので
求めることができなかった. そこで, 代わりに経路の数として考えられる数をすべて列挙することにした.

  ある Taro の家, にんじん, Hanako の家の配置に対してイカの経路数となる整数をイカ数と呼ぶことにする. $K$ 番目に小さいイカ数 (1-indexed) を mod 1,000,000,007 で求めよ.

Constraints

  
$K$ will be between 1 and 1,000,000,000,000,000,000, inclusive.

Input

  入力はイカの形式で与えられる:

  

$K$

Output

$K$ 番目に小さいイカ数を 1,000,000,007 で割った余りを 1 行に出力せよ.

Sample Input 1

5

Sample Output 1

5

Sample Input 2

8

Sample Output 2

9


Sample input:
5


Sample output:
5

Submission status: Accepted

Solution code:
k = int(raw_input())


l,r = 0,k
while (r-l)>1:
	m = (l+r)/2
	if (m * (m + 1)) < k:
		l = m
	else:
		r = m

b = l

#print b
ad = k - (b * (b + 1))

d = ((ad - 1) % (b + 1)) + 1

#print ad,d
x = 2 * b + 1
y = 1
if (ad - d) > 0:
	x += 1
	
if d  <= (b + 1 + 1) / 2:
	dd = d * 2 - 1
else:
	dz = (b + 1 - d)
	dd = dz * 2 + 2

x -= (dd-1)
y += (dd-1)

mod = 1000000007

def mul(a,b):
	res = [[0,0],[0,0]]
	p,q,r = 2,2,2
	for s in xrange(p):
		for t in xrange(q):
			res[s][t] = 0
			for u in xrange(r):
				y = a[s][u] * b[u][t]
				res[s][t] += y
			res[s][t] %= mod
	return res


def fib(x):
	bt = [[1,1],[1,0]]
	r = [[1,1],[1,0]]
	while x > 0:
		if x % 2 != 0:
			r = mul(r,bt)
		bt = mul(bt,bt)
		x /= 2
	
	return r[0][0]
	

#print x,y

ans = fib(x-1) * fib(y-1)
ans %= mod
print ans

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def fibonacci(N, M):
    RA = RD = 1; RB = RC = 0
    XA = XB = XC = 1; XD = 0
    while N:
        if N & 1:
            RA, RB, RC, RD = (RA*XA + RB*XC) % M, (RA*XB + RB*XD) % M, (RC*XA + RD*XC) % M, (RC*XB + RD*XD) % M
        XA, XB, XC, XD = (XA**2 + XB*XC) % M, XB*(XA + XD) % M, XC*(XA + XD) % M, (XB*XC + XD**2) % M
        N >>= 1
    return RC

def solve():
    MOD = 10**9 + 7
    K = int(readline())
    k0 = (int((1 + 4*K)**.5) - 1) // 2
    if k0**2 + k0 == K:
        k0 -= 1
    kk = k0**2+k0
    if K - kk > k0+1:
        m0 = 2*k0+1
        b = K - kk - (k0+1) - 1
    else:
        m0 = 2*k0
        b = K - kk - 1

    if k0//2+1 > b:
        v = fibonacci(2+2*b, MOD) * fibonacci(m0+2-2*b, MOD) % MOD
    else:
        b1 = k0+1 - b-1
        v = fibonacci(3+2*b1, MOD) * fibonacci(m0+1-2*b1, MOD) % MOD
    write("%d\n" % v)
solve()

Submission status: Runtime Error

Solution code:
k = int(raw_input())


l,r = 0,k
while (r-l)>1:
	m = (l+r)/2
	if (m * (m + 1)) < k:
		l = m
	else:
		r = m

b = l

#print b
ad = k - (b * (b + 1))

d = ((ad - 1) % (b + 1)) + 1

#print ad,d
x = 2 * b + 1
y = 1
if (ad - d) > 0:
	x += 1
	
if d  <= (b + 1 + 1) / 2:
	dd = d * 2 - 1
else:
	dz = (b + 1 - d)
	dd = dz * 2 + 2

x -= (dd-1)
y += (dd-1)


def mul(a,b):
	res = [[0,0],[0,0]]
	p,q,r = 2,2,2
	for s in xrange(p):
		for t in xrange(q):
			res[s][t] = 0
			for u in xrange(r):
				y = a[s][u] * b[u][t]
				res[s][t] += y
	return res


def fib(x):
	bt = [[1,1],[1,0]]
	r = [[1,1],[1,0]]
	while x > 0:
		if x % 2 != 0:
			r = mul(r,bt)
		bt = mul(bt,bt)
		x /= 2
	
	return r[0][0]
	

#print x,y

ans = fib(x-1) * fib(y-1)
print ans