桁数1000になる最小のフィボナッチ数は何番目

http://projecteuler.net/index.php?section=problems&id=25
問題。
桁数1000になる最小のフィボナッチ数は何番目。
普通に再帰だと遅かったので、辞書を使う。

# -*- coding:utf-8 -*-

fib = {1:1,2:1}

def Fibonacci(n):
    if n in fib.keys():
        return fib[n]
    else:
        fib[n] = Fibonacci(n-1) + Fibonacci(n-2)
        return fib[n]

def CountDigits(d):
    m = 1
    while True:
        f = Fibonacci(m)
        if len(str(f)) == d:
            return m
        m += 1

print CountDigits(1000)