The first step in any programming competition is to look at the constraints of the problem. Since the parameter, $n$, can be as large as $10^9$ you clearly don't want to waste your time with any program involving loops or recursion and any auxiliary numbers your solution involves almost certainly have to be small (at worst quadratic in the parameter). In other words, there'd better be a closed form solution for this problem involving at most a few expressions that are no worse than quadratic in $n$. Fortunately, there is, but you'll have to wait a bit to see it.
In the tradition of almost all programming challenges, I'll obfuscate things as much as possible, trying to find wording that I (and only I) consider cloyingly cute and nerdy. Imagine, then, a mathematically-inclined butler laying out the silverware according to your specifications (it has to be the butler, obviously, since he's the only household staff member permitted to touch the very expensive silver). The first thing he learned in his training was "serve from the left" (and take away from the right, but that won't come into play now), and that's what we'll do: build strings of "S"s and "F"s, starting at the left, and we'll count the number of possible arrangements, given the rules you laid out.
There are two things to notice: first, starting with an "S" doesn't constrain us in any way, so if we let $A(n)$ count the number of arrangements of $n$ utensils, we'll have immediately that
$$
A(n) = A(n-1) + \text{some other stuff}
$$
where the $A(n-1)$ term counts the number of strings starting with "S" (followed by $n-1$ characters) and the "other stuff" counts the number of strings (of length $n$) starting with "F". The second thing to observe is that if we ever build a substring of the form "...FF", any remaining characters must be "F"s.
Starting, then, with the empty string and adding characters to the right, we'll have the following possibilities at the start:
Working from the top down we see that there are two possible length-$1$ strings, "S" and "F", four possible length-$2$ strings and 6 possible length-$3$ strings. Using the first observation above, we can ignore the left subtree, starting with "S", since that's already taken care of by our recursion.
Now look at the right subtree, enumerating those strings that start with "F". At each level going down we'll have the counts $1$ (for the "F"), $2$ (for "FS" and "FF"), $2$ (for "FSF" and "FFF"), and a bit of thought will convince you that the sequence of the number of possible strings starting with "F" is $\langle 1, 2, 2, 3, 3, 4, 4, 5, 5, \dots\rangle$. That's just the "some other stuff" in the displayed equation above and it's easy to see that it's simply $\lfloor(n+2)/2\rfloor$, where the braces, as usual, delimit the floor function. In other words, we now have a recurrence for the number of arrangements: $A(1)=2$ and for $n>1$,
$$
A(n) = A(n-1) + \left\lfloor\frac{n+2}{2}\right\rfloor
$$
Expanding this, we see with the tiniest bit of algebra that
$$
A(n) = 1+\sum_{k=2}^{n+2}\left\lfloor\frac{k}{2}\right\rfloor
$$
That's good enough for every situation except a programming competition where $n$ may be very large. However, the sum is clearly going to be at most quadratic, so we look for a quadratic closed form for $A(n)$. One final trick comes into play here: because of the division by $2$, we'll have two different forms, depending upon whether $n$ is even or odd. To cut to the chase, it's easy enough to do some polynomial interpolation (twice) and come, at long last to
$$
A(n) = \frac{1}{4}n^2 + n + \begin{cases} 1 & \text{if $n$ is even}\\ 3/4 & \text{if $n$ is odd}\end{cases}
$$