### PROBLEM LINKS:

**Author:** Animesh Fatehpuria

**Testers:** Rajat De Sumit Shyamsukha

**Editorialist:** Animesh Fatehpuria

### DIFFICULTY:

SIMPLE

### PREREQUISITES:

Combinatorics , DP.

### PROBLEM:

Given a number **X** , output the **total number of ways** one can score a score of **X** by hitting only Cannon and In-Off shots. A cannon shot gives **2** points and an In-Off shot gives **3** points.

Since the answer can be very large, Output the answer MOD **1000000009**(10^9+9)

### EXPLANATION:

The best way to approach this problem would be through **DP** and by using **memoization.**

Before we talk about that , let’s look at a naive recursive approach:

Let us define a function **f(x)** which represents Number Of Ways to get a Score Of **X**.

The Important observation is:

**f(x)=f(x-2)+f(x-3);**

After having identified the recursive algorithm , we must identify the base cases:

This is really simple :

A score of **2** can only be achieved in one way by hitting a cannon and a score of **3** can only be achieved in one way by hitting an In-Off.

A score of **1 and 0** cannot be achieved.

The problem with using Recursion to solve this problem is that there will be many OverLapping Subproblems and it will be tremendously inefficient for large VALUES of **X**.

The **Time Complexity** of this approach would be **O(2^X)** which is not feasible at all.

#### OPTIMIZATION

We would use memoization (without recursion)(Iterative Bottom Up DP) to drastically reduce the Time Complexity to **O(N)**.

Memoization requires Creating An **Array** of Size **10^6+1** .

Each Position **Y** in the Array would denote the answer for **X=Y**.

We would **precompute** the answers for each value **Y** where **1<=Y<=1000000** and then answer each query in **O(1)** Time.

We know that **Array[0]=Array[1]=0 and Array[2]=Array[3]=1** .

Following values from **4 to 10^6** would use the relation :

**Array[i]=(Array[i-2]+Arrays[i-3])%(10^9+9);**

After **precomputing** the answers for each **X** we can simply print the answers in **O(1)** Time.