题目描述

小猫咪们在F训练营练习卖萌分身术。每秒每只猫咪都会分身成S+L+R只猫咪,其中S只从当前格子向分身前猫咪面对的方向走一个单位长度,L只猫咪原地不动向左转90度,R只猫咪原地不动向右转90度。每只猫咪都有一个得分——坐标为(x,y)的猫咪的分数为x*y,给出S、L、R。F训练营开始只有一只位于(0,0)、面向(1,0)的猫咪Rainbow,Freda想知道经过N秒后,所有猫咪的分数和。

输入格式

一行四个用空格隔开的整数N,S,L,R,含义如题中所示。

输出格式

一行一个整数,表示经过N秒后Rainbow分身出来的猫咪分数和,由于这个数可能很大,你只需要输出它对1000000007 ( 10^9 +7 ) 取模的结果。

样例输入

3 1 1 0

样例输出

1

样例解释

第一秒:Rainbow分裂成两只小猫咪,一只在(1,0)面向右,一只在(0,0)面向上

第二秒:一共有四只小猫咪,一只在(2,0)面向右,一只在(1,0)面向上,一只在(0,0)面向左,一直在(0,1)面向上

第三秒:一共有8只小猫咪,一只在(2,0)面向上,一只在(3,0)面向右,一只在(1,1)面向上,一只在(1,0)面向左,一只在(0,0)面向下,一只在(-1,0)面向左,一只在(0,2)面向上,一只在(0,1)面向左

只有在(1,1)的那只小猫咪分数为1,所以总分为1

数据范围与约定

对于10%的数据,L=R=0.

对于另外30%的数据,N≤10.

对于100%的数据,1≤N≤10^18,1≤L,R,S≤10^9