I got AC. But I know test that crush my solution;
we need gen Fibonachi
F(0)=0
F(1)=1

from 0 to 33
F(n)=F(n-1)+F(n-2)+1
from 34 to 499
F(n)=F(n-1)

then fill the table
100 500
F(499) F(498) ... F(0)
F(499) F(498) ... F(0)
......................
F(499) F(498) ... F(0)

also test
100 500
F(0) F(1) ... F(499)
F(0) F(1) ... F(499)
......................
F(0) F(1) ... F(499)

Good Luck!

Does the correct answer fits in the 10^9 limit?

Read site news. Thank you for tests.