Codeforces Round #FF Div2 E DZY Loves Fibonacci Numbers

最初みたとき解法が全然わからなかったけど以下の2点に気づくだけだった
フィボナッチ数列同士を足した数列もフィボナッチ数列である
・初項、第2項がa,bのフィボナッチ数列の第n項は基本のフィボナッチ数列をfib[n]としてa*fib[n-1]+b*fib[n-2]とO(1)で求められる

あとは適当に遅延評価segtreeを書くだけなんだけどMODの闇にはまってしまって18WA出してしまった。この前もMODのせいでHackされたし気をつけます
99%正しいコードから通すまで2日かけてしまった。最高の夏の幕開けが…
デバッグ用の関数消すのめんどくさかったんで許してください

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
#define MOD 1000000009
const int SIZE=1<<19;
ll fib[300100];
int n,m;
ll lazy1[SIZE*2],lazy2[SIZE*2];
ll sum[SIZE*2];
void compute_fib()
{
	fib[1]=1ll;
	fib[2]=1ll;
	for(int i=3;i<=300000;i++)fib[i]=(fib[i-1]+fib[i-2])%MOD;
	return;
}
ll compute_num(ll a,ll b,int n)
{
	if(n==1)return a;
	if(n==2)return b;
	return ((a*fib[n-2])%MOD+(b*fib[n-1])%MOD)%MOD;
}
void init()
{
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++)scanf("%I64d",&sum[SIZE-1+i]);
	for(int i=SIZE-2;i>=0;i--)sum[i]=(sum[i*2+1]+sum[i*2+2])%MOD;
	return;
}
void lazy_evaluate(int k,int l,int r)
{
	if(lazy1[k]||lazy2[k])
	{
		sum[k]+=compute_num(lazy1[k],lazy2[k],r-l+2)-lazy2[k];
		while(sum[k]<0)sum[k]+=MOD;
		sum[k]%=MOD;
	}
	if(k<SIZE-1)
	{
		lazy1[k*2+1]+=lazy1[k];
		lazy2[k*2+1]+=lazy2[k];
		lazy1[k*2+1]%=MOD;
		lazy2[k*2+1]%=MOD;
		lazy1[k*2+2]+=compute_num(lazy1[k],lazy2[k],(l+r)/2-l+1);
		lazy1[k*2+2]%=MOD;
		lazy2[k*2+2]+=compute_num(lazy1[k],lazy2[k],(l+r)/2-l+2);
		lazy2[k*2+2]%=MOD;
	}
	lazy1[k]=0;
	lazy2[k]=0;
	return;
}
void update(int a,int b,int sa,int sb,int k,int l,int r,ll x1,ll x2)
{
	lazy_evaluate(k,l,r);
	if(r<=a||b<=l)return;
	else if(a<=l&&r<=b)
	{
		lazy1[k]=x1;
		lazy2[k]=x2;
		lazy_evaluate(k,l,r);
	}
	else
	{
		if(sb<=(l+r)/2)
		{
			update(a,b,sa,sb,k*2+1,l,(l+r)/2,x1,x2);
			lazy_evaluate(k*2+2,(l+r)/2,r);
		}
		else if(sa>=(l+r)/2)
		{
			lazy_evaluate(k*2+1,l,(l+r)/2);
			update(a,b,sa,sb,k*2+2,(l+r)/2,r,x1,x2);
		}
		else
		{
			ll nx1=compute_num(x1,x2,(l+r)/2-sa+1);
			ll nx2=compute_num(x1,x2,(l+r)/2-sa+2);
			update(a,b,sa,(l+r)/2,k*2+1,l,(l+r)/2,x1,x2);
			update(a,b,(l+r)/2,sb,k*2+2,(l+r)/2,r,nx1,nx2);
		}
		sum[k]=(sum[k*2+1]+sum[k*2+2])%MOD;
	}
}
ll query(int a,int b,int k,int l,int r)
{
	lazy_evaluate(k,l,r);
	if(r<=a||b<=l)return 0ll;
	else if(a<=l&&r<=b)return sum[k];
	else
	{
		ll lch=query(a,b,k*2+1,l,(l+r)/2);
		ll rch=query(a,b,k*2+2,(l+r)/2,r);
		sum[k]=(sum[k*2+1]+sum[k*2+2])%MOD;
		return (lch+rch)%MOD;
	}
}
void print_tree()
{
	int num=0;
	for(int i=0;i<5;i++)
	{
		for(int j=0;j<(4-i)*4;j++)cout << ' ';
		for(int j=0;j<(1<<i);j++)
		{
			printf("%I64d[%d][%d]  ",sum[num+j],lazy1[num+j],lazy2[num+j]);
		}
		num+=(1<<i);
		cout << endl;
	}
	return;
}
int main()
{
	init();
	compute_fib();
	for(int i=0;i<m;i++)
	{
		int type,l,r;
		scanf("%d %d %d",&type,&l,&r);
		l--;
		if(type==1)update(l,r,l,r,0,0,SIZE,1,1);
		else printf("%I64d\n",query(l,r,0,0,SIZE));
		//print_tree();
	}
	return 0;
}