LILO probably, not FIFO
Not all Windows versions overwrite the boot sector, but I don't know how it is with yours. Writing LILO back is an easy task if you can boot your Linux from a different media (like cdrom or floppy). If you have a blank floppy, use 'mkbootdisk' command (there should be also a graphical tool) to build boot floppy. Test if it brings you your system. If it does, you can reinstall Windows, then use the floppy, boot to Linux and (as root) run 'lilo' command. LILO will overwrite the bootsector.
It's only one of the methods, but I think it's the easiest.