# 题目

## 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 . Give the result modulo 109+7.

# 整数分拆的生成函数

《整数分拆》第 42 页（其中的“部分”就是题目中的“summands”）：

``````using Nemo
n = 10^4; m = 10^9+7
R,x = PowerSeriesRing(ResidueRing(ZZ,m),n+1,"x")
G = prod([1 + x^k for k = 1 : n if k % 4 != 2])
println(sum([coeff(G,i) for i = 1 : n]))
``````

# Euler 五角数定理

``````using Nemo
n = 10^7; m = 10^9+7
z = div(1 + floor(Int64, sqrt(24*n + 1)), 6)
R,x = PowerSeriesRing(ResidueRing(ZZ,m), n+1, "x")
ϕ(a) = sum([(-1)^i*x^div(a*i*(3*i-1),2) for i = -z:z])
G = ϕ(2)^2*ϕ(8)*inv(ϕ(1)*ϕ(4)^2)
println(sum([coeff(G,i) for i = 1:n]))
``````