0%

# Problem 614

## Special partitions 2

An integer partition of a number $n$ is a way of writing $n$ as a sum of positive integers. Partitions that differ only by the order of their summands are considered the same.

We call an integer partition special if 1) all its summands are distinct, and 2) all its even summands are also divisible by 4.
For example, the special partitions of 10 are:

10 = 1+4+5=3+7=1+9

The number 10 admits many more integer partitions (a total of 42), but only those three are special.

Let be $P(n)$ the number of special integer partitions of $n$. You are given that $P(1) = 1$, $P(2) = 0$, $P(3) = 1$, $P(6) = 1$, $P(10)=3$, $P(100) = 37076$ and $P(1000)=3699177285485660336$.

Find $\displaystyle \sum_{i=1}^{10^7}{P(i)}$. Give the result modulo $10^9+7$.

## 特殊分划

$n$的整数分划是指将$n$写成正整数之和。如果两个分划只在相加的顺序上不同，那么就视为相同的分划。

10 = 1+4+5=3+7=1+9