Question: You can decompose a number greater than 0 as a unique sum of positive Fibonacci numbers. In this question we do this by repeatedly subtracting the **largest possible** positive Fibonacci number. E.g.:

```
1 = 1
2 = 2
3 = 3
4 = 3 + 1
12 = 8 + 3 + 1
13 = 13
100 = 89 + 8 + 3

```

Now, I call a *Fibonacci product* the same lists as above, but with the addition replaced by multiplication. For example, \$f(100) = 89 \times 8 \times 3 = 2136\$.

Write a program or function that given a positive integer *n* returns the Fibonacci product of that number.

---

Testcases:

```
1: 1
2: 2
3: 3
4: 3
5: 5
6: 5
7: 10
8: 8
9: 8
42: 272
1000: 12831
12345: 138481852236

```

Answer: 
Perl, ~~69~~ 63 + 4 (`-pl61` flag) = 67 bytes
=============================================

```
#!perl -pl61
while($_){$n=$m=1;($n,$m)=($m,$n+$m)until$m>$_;$_-=$n;$\*=$n}}{

```

Using:

```
> echo 42 | perl -pl61e 'while($_){$n=$m=1;($n,$m)=($m,$n+$m)until$m>$_;$_-=$n;$\*=$n}}{'

```

Ungolfed:

```perl
while (<>) {
# code above added by -p
    # $_ has input value
    # $\ = 1 by -l61
    while ($_ != 0) {
        my $n = 1;
        my $m = 1;
        while ($m <= $_) {
            ($n, $m) = ($m, $n + $m);
        }
        $_ -= $n;
        $\ *= $n;
    }
} {
# code below added by -p
    print;  # prints $_ (undef here) and $\
}

```

[Ideone](http://ideone.com/Bt2ueH).
Haskell, 44 bytes
=================

Yay for mutual recursion:

```
(a&b)c|c<1=1|b>c=a*f(c-a)|d<-a+b=b&d$c
f=0&1

```

* `a` is the previous Fibonacci number
* `b` is the current Fibonacci number
* `c` is the input
* `f` is the desired function

Less golfed:

```
(a & b) c | c == 0    = 1
          | c <  b    = a * f (c-a)
          | otherwise = b & (a + b) $ c
f x = (0 & 1) x

```