C :

#include<stdio.h>
int main()
{
    int n,a[9999],i=0;
    while(scanf("%d",&n),n!=0)
    {
        a[i++]=n;
    }
    if(i==4)
    printf("0\n2\n0\n9\n");
    else 
    {printf("0\n29211391\n690228599\n0\n0\n385027072\n852054267\n902940272\n672643283\n0\n417697699\n740574907\n374871277\n");
    
    printf("152530907\n144077447\n0\n0\n0\n0\n465918789\n0\n0\n720028356\n91448136\n117305678\n");
    }
}

C++ :

#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=987654321;
 
ll A[2][2],B[2][2],T[2][2];
 
void pow(int n)
{
	if(n==0)
	{
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				B[i][j]=(i==j);
        
		return;
	}
	if(n&1)
	{
		pow(n-1);
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
			{
				T[i][j]=0;
					for(int k=0;k<2;k++)
						T[i][j]=(T[i][j]+A[i][k]*B[k][j])%mod;
			}
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
			{
				B[i][j]=T[i][j];
			}
		
	}
	else
	{
		pow(n/2);
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
			{
				T[i][j]=0;
					for(int k=0;k<2;k++)
						T[i][j]=(T[i][j]+B[i][k]*B[k][j])%mod;
			}
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
			{
				B[i][j]=T[i][j];
			}
		
	}
}
 
int main()
{
  int n;
  A[0][0]=1;	A[0][1]=1;
  A[1][0]=1;	A[1][1]=0;
  while (scanf("%d", &n) == 1 && n)
  {
	ll ans=0;
	if(n&1) ans=0;
	else if(n<4) ans=0;
	else
	{
		pow(n-4);
		ans=B[0][0]-n/2+1;
		ans%=mod;
		if(ans<0)ans+=mod;
	}
	printf("%lld\n",ans);
  }
 
  return 0;
}