该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
将正整数 n 表示成一系列正整数之和: n=n1+n2+⋯+nk,
其中 n1≥n2≥⋯≥nk≥1,k≥1。
正整数 n 的这种表示称为正整数 n 的划分。求正整数 n 的不同划分个数。
例如正整数 6 有如下 11 种不同的划分:
6、5+1、4+2,4+1+1、3+3,3+2+1,3+1+1+1、2+2+2,2+2+1+1,2+1+1+1+1、1+1+1+1+1+1 。
输入格式
第一行是测试数据的数目 M(1≤M≤10) 。以下每行均包含一个整数 n(1≤n≤1000)。
输出格式
输出每组测试数据有多少种分法,最终结果模 109+9 。
格式说明输出时每行末尾的多余空格,不影响答案正确性
输入、输出要求要求使用「文件输入、输出」的方式解题,输入文件为 divide.in
,输出文件为 divide.out
样例输入
1
6
样例输出
11