Algo 100 - Appended Fibonacci Sum

Writer: Jakob Degen

Find the last nine digits of the sum of the sequence of numbers created by appending the first n fibonacci numbers, where n ranges from 1 to 50. (The Fibonacci Sequence begins with 1, 1, 2 for the purpose of this problem.) For instance, here are the first few appended Fibonacci numbers:

1, 11, 112, 1123, 11235, 112358, 11235813, ...

You should be adding up the first 50 of these.