521 ACM 来自一只单身狗的表白

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

2018年是农历戊戌年,生肖狗作为今年的吉祥物,表示虽然没赶上昨天的情人节,但看在它对ACM无私的爱上,决定无偿送给大家一道签到题。

 

大家一定很好奇,今天的题目中所包含的动物分明对应着十二生肖,可为什么不是按照顺序给出的呢?别着急,其实这十二道题目的顺序就包含着题目答案的信息。

 

首先我们给出超越数的定义:对于一个数a来说,我们把a^a称为数字a的超越数,例如数字3的超越数是27。

而在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。一个排列中所有逆序总数叫做这个排列的逆序数。

例如排列 1 4 3 2 的逆序数就是 3。

 

十二道题目中所包含的动物按照十二生肖的顺序分别对应着数字1-12,因此它们构成了一个排列B。

现在请你求出排列B的逆序数a,并求出数字a的超越数,那么数字a的超越数即为最后结果。请将最后结果对1667642815取模。

Input

Output

输出一个数,即为题目描述中所得到的答案

Sample Input


				

Sample Output


				

Hint

Source

axuhongbo