题目描述

许多人了解二叉搜索树（BST）。二叉搜索树中的键值总是以满足BST性质的方式存储：

设$x$为二叉搜索树中的一个节点。如果$y$是$x$左子树中的一个节点，则$key[y] \leq key[x]$。如果$y$是$x$右子树中的一个节点，则$key[y] > key[x]$。

例如：

这是一棵二叉搜索树。它可以通过依次插入向量$A = <12, 6, 3, 18, 20, 10, 4, 17, 20>$来构建。但也可以通过向量$B = <12, 18, 17, 6, 20, 3, 10, 4, 20>$来构建。

现在给定一个向量$X$，你可以通过$X$构建一棵二叉搜索树。你的任务是计算有多少个不同的向量可以构建出相同的二叉搜索树。为了简化问题，你只需输出不同向量的数量对$9901$取模的结果。

输入格式

输入包含多个测试用例。每个用例的第一行是一个正整数$n$，表示测试向量的长度。整数$n$小于$100$。接下来的一行包含$n$个小于$10000$的正整数。输入以$n = 0$的用例结束，该用例无需处理。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示不同向量的数量对$9901$取模的结果。

样例输入

3
2 1 3
9
5 6 3 18 20 10 4 17 20
0

样例输出

2
168

题目来源

POJ Monthly--2006.03.26, newton