#P18382. Alternative Accounts 2
Alternative Accounts 2
Alternative Accounts 2
题目描述
在一场钓鱼比赛中,共有 名选手报名,每名选手恰好注册了两个不同账号,合计 个账号。所有选手都遵守同一条规则:每次参赛时,必须使用自己两个账号中当前排名较差的那个。排名数字越小越好,因此,若两个账号的当前排名分别为 ,该选手只能使用排名为 的账号参赛。
按初始排名将账号编号为 。设 表示当前排名第 的账号,最初有 。
之后进行了 场比赛,每场恰有一名选手参赛。第 场比赛中,当前排名为 的账号参赛,并上升一名,即交换 与 。保证 。
给定全部比赛记录,求有多少种方法将这 个账号划分成 个无序的二元组,使每个二元组代表同一名选手的两个账号,并且在每场比赛发生时,参赛账号都确实是该组中当前排名较差的账号。
两个划分不同,当且仅当至少有一个账号在两个划分中的同组选手账号不同。选手没有额外编号,二元组内部和二元组之间的排列顺序都不产生新的方案。
答案对 取模。
输入格式
第一行包含两个整数 (),分别表示选手人数与比赛场数。
接下来 行,每行包含一个整数 (),表示第 场参赛账号在该场比赛开始前的当前排名。
本题输入只有一组数据。
输出格式
输出一个整数,表示符合全部记录的账号配对方案数模 的结果。
样例输入 1
1 1
2
样例输出 1
1
样例输入 2
2 2
2
3
样例输出 2
0