给定一个长度为
- 每个数
要么被染成红色,要么被染成绿色。 - 红色的数从左到右依次严格递增,绿色的数从左到右依次严格递减。
例如:
如果一个数组至少存在两个不同的优秀的染色方案,那么称这个数组是完美的。(两个染色方案不同当且仅当至少存在一个位置上的数字被染成不同的颜色)。
例如,
补充说明:如果红色的数只有
我们定义一种给染色方案打分的方式。
对于每个的有序元素对
- 如果
染成红色,且 ,则该元素对得 分; - 如果
染成绿色,且 ,则该元素对得 分; - 不满足 1 或 2 ,则该元素对得
分。
则一个染色方案的得分为所有有序元素对的得分和。
一个完美的数组的得分为它所有优秀的染色方案的得分的最大值。
现在确定数组
- 第一问:有多少种确定
中后 个数的方案使得 是一个完美数组? - 第二问:所有可能的完美数组的得分和是多少?
由于答案太大,你只需要输出答案在模
输入格式
本题有多组测试数据。
输入的第一行包含一个正整数
接下来包含
第一行包含三个整数
第二行包含
输出格式
对于每组测试数据输出一行包含两个用单个空格隔开的整数。
第一个整数表示优秀数组的数量模
的值;第二个整数表示优秀数组的得分之和模
的值。
样例一
input
5 6 10 6 1 9 3 4 7 6 5 8 4 1 7 2 6 9 10 2 3 6 6 11 6 1 7 5 8 3 9 9 10 5 5 10 6 4 7
output
1 63 8 245 29378 1267731 1 17 78 1820
样例二
见附件。
评分方式
每个测试点
每一行应按顺序输出两问的答案,不符合输出格式的输出得
程序仅回答对第一问得
如果你不回答第一问或第二问,也需要在对应位置上输出任意一个整数以满足输出格式。
数据范围
对于所有的数据,保证:
时间限制:3s
空间限制: