Chiaki is interested in an infinite sequence a1,a2,a3,..., which is defined as follows:
an={1 n=1,2
an−an−1+an−1−an−2 n>2
}
Chiaki would like to know the sum of the first n terms of the sequence, i.e. ∑i=1nai. As this number may be very large, Chiaki is only interested in its remainder modulo (109+7).