题目描述

哈蒙有$n$条导线排成一排，每条导线有一个电阻值，神奇的电光只能从一根导线传到电阻比它大的上面，而且必须从左边向右传导，当然导线不必是连续的。 哈蒙想知道电光最多能通过多少条导线，还想知道这样的方案有多少。

输入

第一行两个整数$n$和$type$。$type$表示数据类型。 第二行$n$个整数表示电阻。

输出

第一行一个整数表示电光最多能通过多少条导线。 如果$type=1$则需要输出第二行，表示方案数对$123456789$取模。

输入样例

5 1
1 3 2 5 4

输出样例

3
4

提示

【数据规模及约定】 对于20%的数据，$n≤10$。 对于40%的数据，$n≤1000$。 对于另外20%的数据，$type=0$。 对于另外20%的数据保证最多能通过不超过$100$条导线。 对于100%的数据$n≤100000$，电阻值不超过$100000$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。