Welcome to recursion. One of the most easiest things to code but really hard to debug! Recursion is a very powerful tool to solve problems. All loops(while, for , do while) can be simulated using recursion. Also the main step of the dynamic programming is recursion which is useful in solving many algorithmically difficult problems. Lets solve some problems now.

Problem 1:

You are given scales for weighing loads. On the left side lies a single stone of known weight W < 2N. You own a set of N different weights, weighing 1, 2, 4, ..., 2^N-1 units of mass respectively. Determine how many possible ways there are of placing some weights on the sides of the scales, so as to balance them (put them in a state of equilibrium).

Input Specification

The input line contains two integers: N W, where N denotes the number of weights and W represents the weight to be placed on the left side.

Output Specification

Output must be a single integer denoting the number ways in which one can balance the weight W by placing weights on any side.

Sample Input and Output

Input: 2 4
Output: 3
Input: 5 10
Output: 14

Problem 2:

Given a weighing pan, n weights and a destination weight D, print "YES" or "NO" depending whether you can weight D using other weights given.

Input Specification

Input begins with numbers of weights n, then n values denoting mass of each weight and then in the end destination weight D.

Output Specification

As the output, print "YES" if it is possible to weight D, otherwise "NO".

Sample Input and Output

Input: 3 1 3 4 2 Output: YES Input: 2 1 3 5 Output: NO