Problem

Source: Tuymaada Junior 2006 p6

Tags: number theory, combinatorics, Sum



Palindromic partitioning of the natural number $ A $ is called, when $ A $ is written as the sum of natural the terms $ A = a_1 + a_2 + \ ldots + a_ {n-1} + a_n $ ($ n \geq 1 $), in which $ a_1 = a_n , a_2 = a_ {n-1} $ and in general, $ a_i = a_ {n + 1 - i} $ with $ 1 \leq i \leq n $. For example, $ 16 = 16 $, $ 16 = 2 + 12 + 2 $ and $ 16 = 7 + 1 + 1 + 7 $ are palindromic partitions of the number $16$. Find the number of all palindromic partitions of the number $2006$.