Description

题目背景

动物们都受到了《英格兰动物之歌》的鼓舞，决定联合起来反抗农夫们的剥削，但是动物们需要先储备战略资源。

题目描述

动物们需要先储备战略资源，在英格兰大陆上分布着许多资源供给站，每个被激活的供给站每秒会产生一克拉的战略资源，但是每秒只有一个供给站的门能被打开，然后动物会拿走里面所有的资源。每个供给站第一次被开门时它将会被激活，对于每个供给站，除了第一次开门外，每次开门都需要消耗供给站内一克拉的战略资源，剩余的资源可以被动物拿走，同一个供给站连续x秒开门需要视作开门x次，即每秒都会开门然后关上。

英格兰动物世界有自己的计时标准，与人类世界的年月日时分秒类似，它们的时间由n个计时单位组成，第i个时间单位逢ti进一，从0开始计数。动物们通过观察发现了每一秒是哪个供给站开门的规律，这同样与时间有关，供给站的编号由m个数字组成，任意一个数字不同则代表是不同的供给站，这m个数字对应的是英格兰动物世界时间进制上的其中m位，第i位对应的是当前第xi个时间单位上的值。比如n=6，ti=10000,12,30,24,60,60，m=3，xi=1,4,5，则当时间为(2019,7,26,9,59,59)时，编号为(2019,9,59)的供给站的门将会打开，下一秒的时间为(2019,7,26,10,0,0)，编号为(2019,11,0)的供给站的门将会打开。

革命的领导者雪球和拿破仑想知道从初始时间到终止时间一共能获得多少克拉的战略资源？起始时间的定义为所有时间单位都是零，终止时间的定义为所有时间单位都处于即将进位的数字，如(9999,11,29,23,59,59)。

Input Format

第一行两个整数，表示计数单位个数n和供给站编号位数m。

第二行n个整数，表示时间进制ti，第一位是最大的时间单位，往后依次更小，第n个时间单位是秒。

第三行m个整数，xi表示供给站编号的第i位为对应时间的第xi位，可能重复，不保证有序。

Output Format

一个整数，表示能获得的战略资源克拉数，由于答案可能很大，故输出答案模P=19961107的结果。

Sample

样例输入

3 1
2 3 4
2

样例输出

24

Hint